[백준] 2667번 - 단지번호붙이기 (DFS, BFS) - 결과 포함

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

이 문제는 연결되어 있는 정점끼리 분류하는 문제이다.

연결되어 있는 정점들의 그룹이 몇 개가 있고, 그 그룹들 안에는 각각 정점이 몇 개가 있는지를 출력하는 문제이다.

 

먼저 이 그래프를 탐색할 때 어느 방향으로 이동이 가능한지를 정해야 한다.

이번 문제에서는 인접해 있는 모든 정점을 살펴보아야 하므로 상, 하, 좌, 우 모두 이동이 가능하다.

 

또한 시작하는 정점을 정해야한다. 이번 문제에서는 어느 지점에 건물이 있는지 알 수 없으므로 모든 정점을 살펴보아야 했다.

그러나 이 때, 이미 방문했던 건물은 굳이 다시 방문할 필요가 없었다. 방문했다는 것은 이미 그 주변의 건물들을 방문했고, 단지를 정했다는 의미이기 때문이다.

 

아직 방문하지 않은 모든 정점에 대해서 BFS를 수행하도록 했다.

그래프 범위를 벗어나거나 이미 방문한 정점을 제외하고 방문하지 않은 정점을 방문할 때마다 카운트를 1 증가시켰다.

이 카운트는 현재 세고 있는 단지의 건물 갯수를 의미한다.

 

한 번의 BFS가 끝날 때마다 결과를 결과 리스트에 추가했다.

총 몇 개의 단지가 있는지, 단지의 건물 갯수가 필요했기 때문이다.

 

[소스코드]

from collections import deque

n = int(input())

graph = list()

for i in range(n):
    graph.append(list(map(int, input())))

result = []

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(x, y):
    queue = deque()
    queue.append([x, y])
    graph[x][y] = 0
    count = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                count += 1
                graph[nx][ny] = 0
                queue.append([nx, ny])
    return count


for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            cnt = 0
            cnt = bfs(i, j)
            result.append(cnt)

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