코딩 테스트

얼음 틀 채우기와 연결 요소

#BOJ 2667 · 문제 원문 ↗ Flood fill · BFS / DFS · Connected components

얼음 틀의 빈칸에 물을 부으면 상하좌우로 이어진 곳이 한 덩어리가 됩니다. 이 덩어리가 그래프의 연결 요소입니다. BOJ 2667 「단지번호붙이기」에서는 같은 생각으로 연결된 집을 묶고, 단지 수와 각 단지의 크기를 구합니다.

아래 얼음 틀은 이 해설에서 만든 예제입니다. 먼저 묶음 수를 예상하고 재생해 보세요. 「단지 · 1 묶기」로 바꾸면 채울 대상만 0에서 1로 바뀝니다.

INTERACTIVE LAB얼음 틀과 연결 요소

현재 상태

풀이의 핵심

  1. 전체 칸을 순서대로 훑습니다. 대상 칸이고 아직 발견하지 않았다면 새 묶음을 시작합니다.
  2. 스택(DFS)이나 큐(BFS)에 넣을 때 방문 표시를 합니다. 그래야 여러 이웃이 같은 칸을 중복으로 넣지 않습니다.
  3. 상하좌우의 연결된 칸을 모두 처리하며 크기를 셉니다. 탐색이 끝나면 다음 미방문 칸을 찾습니다.
  4. 모은 크기를 오름차순으로 정렬합니다.

첫 예제의 결과는 4개, 크기 [2, 4, 4, 4]입니다. 탐색 한 번은 시작점에서 닿는 칸을 빠짐없이 찾고, 벽 너머의 칸에는 갈 수 없습니다. 따라서 한 번의 탐색이 정확히 한 연결 요소를 만듭니다. BFS와 DFS는 처리 순서만 다릅니다.

복잡도와 주의점

N × N 지도와 K개 단지에서 탐색은 O(N²), 결과 정렬은 O(K log K)입니다. 전체 시간은 O(N² + K log K), 추가 공간은 O(N²)입니다. 아래 코드는 반복형 DFS를 사용하므로 긴 연결 구간에서도 재귀 깊이 제한에 의존하지 않습니다.

대각선만 닿는 칸은 같은 단지가 아닙니다. 실험에서 대각선 예제를 고르면 13개로 나뉩니다. 얼음 틀은 0, BOJ 풀이는 1을 탐색한다는 차이도 확인하세요. 화면의 단계 기록은 설명을 위한 추가 메모리이며 제출 코드에는 없습니다.

직접 작성한 풀이 코드

Python 3 
import sys


def component_sizes(grid):
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    sizes = []
    for r in range(n):
        for c in range(n):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            stack = [(r, c)]
            seen[r][c] = True
            size = 0
            while stack:
                y, x = stack.pop()
                size += 1
                for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                    ny, nx = y + dy, x + dx
                    if (0 <= ny < n and 0 <= nx < n
                            and grid[ny][nx] == '1' and not seen[ny][nx]):
                        seen[ny][nx] = True
                        stack.append((ny, nx))
            sizes.append(size)
    return sorted(sizes)


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    grid = [sys.stdin.readline().strip() for _ in range(n)]
    sizes = component_sizes(grid)
    print(len(sizes))
    print(*sizes, sep='\n')

참고 자료와 다음 실험