백준 2667 단지번호붙이기(BFS, DFS)

 

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

문제를 보면 그래프 문제라는걸 바로 알 수 있고 dfs, bfs로 풀어야함을 알 수 있다.

 

0으로 구분되어져 있는 단지는 몇개인지 모르기 때문에 처음 1을 찾아줘서 거기서 탐색을 진행해 0으로 만들어주면

 

다음 단지를 찾을 때 방금 탐색했던 단지는 고려하지 않아도 됨을 알 수 있다.

 

BFS 이용

from collections import deque

def bfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque()
    queue.append((x, y))
    board[x][y] = 0
    res = 1
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            if board[nx][ny] == 1:
                board[nx][ny] = 0
                queue.append((nx, ny))
                res += 1
    return res

n = int(input())

board = []
data = []
for _ in range(n):
    board.append(list(map(int,input())))
for i in range(n):
    for j in range(n):
        if board[i][j] == 1:
            data.append(bfs(i, j))
data.sort()

print(len(data))
for i in range(len(data)):
    print(data[i])

DFS 이용

def dfs(x,y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    global res
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]

    if board[x][y] == 1:
        res += 1
        board[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx,ny)
        return 1
    return 0

n = int(input())

board = []
data = []
for _ in range(n):
    board.append(list(map(int,input())))

res = 0
for i in range(n):
    for j in range(n):
        if board[i][j] == 1:
            if dfs(i,j) == 1:
                data.append(res)
                res = 0

print(len(data))
data.sort()
for i in data:
    print(i)