백준 문제 풀이 - 단지번호붙이기 2667번

📜 문제 이해하기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

💡 문제 재정의

모여있는 단지들끼리 묶은 후 오름차순으로 단지안에 있는 집들의 수를 출력하라.

✏️ 계획 수립

bfs를 사용하면 문제를 해결할 수 있다. (0,0)에서부터 (N-1, N-1)까지 확인하면서 집이 있는지 확인한 후 집이 존재한다면 bfs를 수행하여 몇개의 집이 뭉쳐있는지 확인 후 결과 배열에 저장한다. 모든 작업이 끝난 후 결과 값을 오름차 순으로 정렬하고 순서대로 출력하면 된다.

💻 계획 수행

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())
    city = []
    visited = [[0 for _ in range(N)] for _ in range(N)]
    open_set = []
    result = []
    count = 0

    for _ in range(N):
        city.append(list(map(int, sys.stdin.readline().rstrip())))

    for i in range(N):
        for j in range(N):
            if city[i][j] == 1 and visited[i][j] == 0:
                open_set.append([i, j])
                visited[i][j] = 1
                count += 1

            while open_set:
                y, x = open_set.pop(0)
                if y - 1 >= 0 and city[y - 1][x] == 1 and visited[y - 1][x] == 0:
                    open_set.append([y - 1, x])
                    visited[y - 1][x] = 1
                    count += 1
                if y + 1 < N and city[y + 1][x] == 1 and visited[y + 1][x] == 0:
                    open_set.append([y + 1, x])
                    visited[y + 1][x] = 1
                    count += 1
                if x - 1 >= 0 and city[y][x - 1] == 1 and visited[y][x - 1] == 0:
                    open_set.append([y, x - 1])
                    visited[y][x - 1] = 1
                    count += 1
                if x + 1 < N and city[y][x + 1] == 1 and visited[y][x + 1] == 0:
                    open_set.append([y, x + 1])
                    visited[y][x + 1] = 1
                    count += 1
            if count > 0:
                result.append(count)
                count = 0
    print(len(result))
    print(*sorted(result), sep='\n')

🤔 회고

먼저 집이 있는지 하나하나 보는 작업은 O(N²)이 된다. 이 때 집을 발견했을 때 bfs는 O(V²)이 된다. 집이 있는지 찾아보는 위 작업에서 이미 방문한 집은 bfs를 수행하지 않기에 최종 시간 복잡도는 O(N²)이 된다. 이 문제의 입력은 5<=N<=25이 이기에 파이썬으로 구현해도 충분한 시간이 된다.