그래프 탐색 - BFS 와 DFS

이 장에서 배우는 것

앞 장에서는 지금 고른 선택이 전체 결과에도 유리한지 따졌다. 이번에는 선택의 좋고 나쁨보다 먼저, 어떤 곳에서 어떤 곳으로 이동할 수 있는지를 살펴본다. 사무실 사이의 연락 관계, 창고 통로, 지도에서 이어진 땅은 모두 연결 관계로 표현할 수 있다. 연결을 따라가며 필요한 대상을 빠짐없이 확인하는 과정이 그래프 탐색이다.

탐색의 핵심은 다음에 확인할 대상을 어디에 보관하는가와 이미 확인한 대상을 어떻게 구분하는가에 있다. 같은 연결 관계라도 먼저 들어온 대상을 꺼내면 가까운 곳부터 살피고, 나중에 들어온 대상을 꺼내면 한쪽으로 깊게 따라간다. 이 차이가 미로의 최단 거리와 섬 개수처럼 서로 다른 질문을 해결한다.

• 연결 관계를 인접 리스트로 표현하고, 방문 표시가 중복 처리를 막는 이유를 설명한다.
• 너비 우선 탐색(Breadth-First Search, BFS)으로 이동 비용이 같은 미로의 최단 거리를 구한다.
• 깊이 우선 탐색(Depth-First Search, DFS)을 반복문과 재귀 함수로 구현한다.
• 격자를 그래프로 해석하고, 연결 요소를 세어 섬 개수를 구한다.
• 작은 격자의 모든 배치를 만들어 서로 다른 풀이의 결과를 대조한다.

문제 상황

작은 물류 작업장의 바닥을 격자로 기록한다고 하자. 각 칸의 값이 1이면 사람이 지나갈 수 있고, 0이면 설비 때문에 지나갈 수 없다. 작업자는 왼쪽 위 칸에서 오른쪽 아래 칸으로 이동하려 한다. 한 번에 상하좌우로 한 칸만 움직일 수 있으며 대각선 이동은 허용하지 않는다. 출발 칸이나 도착 칸이 막혀 있거나 서로 이어져 있지 않으면 이동할 수 없다.

첫 번째 문제는 이 작업장에서 필요한 최소 이동 횟수를 구하는 일이다. 출발 칸에 서 있는 상태의 이동 횟수는 0이다. 따라서 출발 칸과 도착 칸이 같고 그 칸이 열려 있다면 답은 0이다. 방문한 칸 수를 답으로 삼으면 이동 횟수보다 1이 커지므로 처음부터 기준을 분명히 정해야 한다.

두 번째 문제는 임시 보관 구역을 묶는 일이다. 다른 격자에서 1은 물품을 놓을 수 있는 땅이고 0은 빈 통로다. 상하좌우로 이어진 땅을 하나의 섬으로 취급한다. 대각선으로만 닿은 땅은 서로 다른 섬이다. 이 문제에서는 어느 칸이 더 가까운지가 아니라, 서로 이어진 묶음이 몇 개인지가 중요하다.

격자로 들어가기 전에 세 번째로 작은 연락망 문제를 생각한다. 작업 구역 A부터 F까지가 있고, 직접 연락할 수 있는 쌍은 A와 B, A와 C, B와 D, C와 D, E와 F다. 연락을 여러 번 전달해도 좋을 때 전체 구역은 몇 묶음으로 나뉘는가. 이 짧은 문제로 연결 표현과 방문 표시를 먼저 익힌다. 완성 프로그램에서는 앞의 두 격자 문제를 해결하고, 작은 입력을 모두 만들어 검증한다.

연결 관계와 방문 표시

인접 리스트로 이웃을 기록한다

그래프는 대상인 정점과 두 대상을 잇는 간선으로 이루어진다. 연락망에서는 구역 하나가 정점이고 직접 연락 가능한 관계가 간선이다. 이 예제의 연락은 양방향이므로 A에서 B로 갈 수 있으면 B에서 A로도 갈 수 있다. 이를 무방향 그래프라고 한다.

인접 리스트는 각 정점에 바로 연결된 이웃을 모은 표현이다. 정점 이름이 문자열이면 딕셔너리의 값에 리스트를 넣을 수 있다. 아래의 각 리스트 순서는 탐색 순서를 일정하게 만드는 역할도 한다.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
    "E": ["F"],
    "F": ["E"],
}

무방향 간선 하나는 양쪽 리스트에 한 번씩 기록한다. 이웃이 없는 정점도 빈 리스트로 남겨 두어야 한다. 관계가 없다는 이유로 정점을 통째로 생략하면, 혼자 떨어진 구역을 묶음 개수에서 빠뜨릴 수 있다. 정점이 0부터 시작하는 정수라면 딕셔너리 대신 리스트 안에 리스트를 두어도 같은 원리로 동작한다.

서로 연결을 따라 도달할 수 있는 정점들의 최대 묶음을 연결 요소라고 한다. 그림의 연락망은 연결 요소가 두 개다. A에서 탐색하면 A, B, C, D를 모두 확인할 수 있지만 E나 F에는 도달하지 못한다. 아직 방문하지 않은 E에서 탐색을 한 번 더 시작해야 한다.

방문 표시는 발견할 때 한다

방문 표시는 이미 탐색 대상으로 등록한 정점을 기억하는 장치다. A에서 B로 이동한 뒤 B의 이웃인 A를 다시 등록하면 같은 길을 계속 오갈 수 있다. 방문 집합이나 방문 배열을 두고, 아직 표시하지 않은 이웃만 등록하면 이 반복을 막을 수 있다.

여기서 방문은 처리가 끝났다는 뜻으로 한정하지 않는다. 앞으로 처리하기로 예약했다는 뜻도 포함한다. 큐나 스택에 넣는 순간 방문 표시를 하면, 다른 정점에서 같은 이웃을 발견해도 다시 넣지 않는다. 예를 들어 B와 C가 모두 D를 이웃으로 가지더라도 D는 한 번만 등록된다.

seen = {"A"}
stack = ["A"]

while stack:
    node = stack.pop()
    for neighbor in graph[node]:
        if neighbor not in seen:
            seen.add(neighbor)
            stack.append(neighbor)

이 코드는 리스트 끝에서 꺼내므로 반복 DFS다. A를 꺼내 B와 C를 차례로 넣으면 C가 먼저 나온다. 이후 D, B를 처리한다. 스택에 남아 있던 B는 이미 발견 표시가 되어 있으므로 D에서 다시 넣지 않는다. 이 구현은 도달 가능한 정점을 찾는 데 적합하지만, 꺼내는 순서가 재귀 DFS의 진입 순서와 같다고 가정해서는 안 된다.

정확성의 근거는 두 문장으로 정리할 수 있다. 등록한 모든 정점은 시작점에서 연결을 따라 도달할 수 있다. 또 도달 가능한 정점이 빠졌다고 가정하면, 시작점에서 그 정점으로 가는 경로 어딘가에 방문한 정점과 방문하지 않은 정점이 처음 맞닿는 간선이 있어야 한다. 방문한 쪽을 처리할 때 반대쪽을 등록하므로 그런 누락은 생기지 않는다.

정점 수를 V, 간선 수를 E라고 쓰자. 전체 그래프를 인접 리스트로 탐색하면 각 정점을 한 번 처리하고 각 리스트 항목을 한 번 확인하므로 시간은 O(V + E)다. 무방향 간선은 두 번 확인하지만 상수 배수라서 표기는 같다. 인접 리스트 저장 공간은 O(V + E)이고, 방문 표시와 탐색 대기 공간은 O(V)다.

BFS로 격자의 최단 거리 구하기

격자는 이웃을 계산하는 그래프다

격자의 열린 칸 하나를 정점으로 보고 상하좌우의 열린 칸끼리 간선을 연결하면 그래프가 된다. 다만 모든 칸의 이웃 리스트를 따로 저장할 필요는 없다. 현재 좌표가 (r, c)라면 (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)을 계산하면 된다. 이웃 후보 중 격자 범위 안에 있으며 값이 1인 칸만 실제 이웃이다.

미로 문제의 모든 이동은 비용이 1로 같다. 이런 그래프에서는 먼저 들어온 칸을 먼저 꺼내는 큐를 사용하면 가까운 칸부터 처리할 수 있다. 시작점의 거리를 0으로 두고, 거리 d인 칸에서 처음 발견한 이웃에 d + 1을 기록한다. 거리 배열의 초기값을 -1로 두면 아직 발견하지 않았다는 표시도 함께 맡길 수 있다.

손으로 따라갈 예시는 2행 3열 격자다. 첫째 행은 110, 둘째 행은 011이다. 시작점은 (0, 0), 도착점은 (1, 2)다. 큐는 왼쪽에서 꺼내며, 이웃은 위, 아래, 왼쪽, 오른쪽 순서로 확인한다.

큐에는 이동 횟수가 작은 칸부터 들어간다

단계	꺼낸 칸과 거리	새로 등록한 칸	처리 뒤 큐
초기	없음	(0, 0), 거리 0	[(0, 0)]
1	(0, 0), 0	(0, 1), 거리 1	[(0, 1)]
2	(0, 1), 1	(1, 1), 거리 2	[(1, 1)]
3	(1, 1), 2	(1, 2), 거리 3	[(1, 2)]
4	(1, 2), 3	도착하여 종료	[]

처음 기록한 거리가 최단인 이유

BFS의 불변식은 큐에서 꺼내는 거리 값이 감소하지 않는다는 것이다. 처음에는 거리 0인 시작점만 있다. 거리 d인 칸을 처리하면 새 이웃은 모두 거리 d + 1로 큐 뒤에 들어간다. 이미 앞에 있던 칸보다 먼저 처리되지 않으므로 가까운 거리의 처리가 앞선다.

어떤 칸에 처음 기록한 거리가 d라고 하자. 그보다 짧은 경로가 있다면, 그 경로에서 바로 앞 칸의 거리는 d - 1보다 작아야 한다. 그 앞 칸은 더 일찍 처리되어 해당 칸을 먼저 발견했을 것이므로 모순이다. 따라서 처음 발견할 때 기록한 거리를 나중에 고칠 필요가 없다. 도착점을 큐에서 꺼내면 그 거리로 답할 수 있다.

이 근거는 간선마다 이동 비용이 같다는 조건에 기대고 있다. 어떤 통로는 1분, 다른 통로는 4분 걸린다면 간선 수가 적은 경로와 총시간이 짧은 경로가 달라진다. 그 경우의 최단 경로는 다음 장에서 다룬다. 여기서는 모든 한 칸 이동의 비용을 1로 고정한다.

격자가 R행 C열이면 칸마다 이웃 후보를 네 번 확인한다. 따라서 최악의 시간 복잡도는 O(RC)이고, 거리 배열과 큐를 포함한 추가 공간 복잡도도 O(RC)다. 도착점을 빨리 찾으면 실제 확인하는 칸은 줄어들 수 있지만 최악의 범위는 그대로다.

DFS로 섬 개수 구하기

탐색을 시작한 횟수가 답이 된다

섬 문제에서는 모든 칸을 행 순서대로 살핀다. 물이거나 이미 방문한 땅이면 넘어간다. 아직 방문하지 않은 땅을 만나면 섬 개수를 1 늘리고, 그 칸에서 연결된 모든 땅을 탐색한다. 탐색이 끝나면 같은 섬의 다른 칸에서는 다시 탐색을 시작하지 않는다.

예를 들어 첫째 행이 101, 둘째 행이 110인 격자를 보자. (0, 0)에서 시작하면 (1, 0)과 (1, 1)까지 방문한다. (0, 2)는 이 묶음과 대각선으로만 닿으므로 별도의 섬이다. 전체 칸을 살피며 탐색을 시작하는 횟수는 두 번이다.

이 방법의 불변식은 바깥 반복문이 다음 칸을 검사하기 전에, 이미 시작한 각 섬의 모든 땅이 방문 표시되어 있다는 것이다. 탐색 한 번은 연결된 땅만 방문하므로 서로 다른 섬을 합치지 않는다. 또한 연결된 땅을 빠짐없이 방문하므로 같은 섬을 다시 세지 않는다. 모든 땅은 결국 바깥 반복문에서 검사되므로 빠진 섬도 없다.

반복 DFS와 재귀 DFS의 선택

반복 DFS는 다음에 처리할 좌표를 리스트에 넣고 pop()으로 꺼낸다. 재귀 DFS는 이웃을 발견할 때 함수를 호출하고, 그 호출이 끝나면 원래 칸으로 돌아온다. 재귀에서는 되돌아갈 위치를 함수 호출 스택이 보관한다. 두 방식 모두 방문 표시가 필요하다.

섬 개수만 필요하다면 BFS를 써도 답은 같다. 연결 요소를 모두 방문하는 것이 목적이기 때문이다. DFS를 사용한다고 해서 최단 거리가 구해지는 것은 아니다. DFS가 처음 찾은 경로는 이웃을 살피는 순서에 따라 길게 우회할 수 있다. 거리 질문과 연결 여부 질문을 구분해야 한다.

길게 이어진 땅에서는 재귀 호출 깊이가 땅의 개수만큼 늘어날 수 있다. 실행 환경의 재귀 깊이 제한을 넘으면 오류가 발생한다. 완성 코드에서는 반복 DFS를 기본 풀이로 삼고, 재귀 DFS는 작은 입력의 대조에 사용한다. 제한값을 크게 바꾸는 것으로 입력 크기 문제를 해결하려 하지 않는다.

전체 칸 검사와 각 땅의 이웃 확인을 합쳐 시간은 O(RC)다. 방문 배열과 명시적 스택을 쓰는 반복 DFS의 추가 공간은 O(RC)다. 재귀 DFS도 방문 배열뿐 아니라 최대 O(RC)의 호출 공간을 사용할 수 있다. 입력 격자를 직접 지우는 방식도 가능하지만, 여기서는 같은 입력으로 여러 풀이를 비교하기 위해 원본을 보존한다.

완성 코드

아래 내용을 main.py로 저장한다. 입력 형식은 첫 줄에 행 수와 열 수를 쓰고, 이어지는 각 줄에 0과 1을 공백 없이 적는 방식이다. 예시 문자열을 io.StringIO로 감싸 코딩 테스트의 줄 단위 입력을 흉내 낸다. 입력은 양의 크기의 직사각형이며 0과 1로만 이루어진다고 가정한다.

느린 미로 풀이는 큐를 쓰지 않는다. 모든 칸의 거리 후보를 반복해서 갱신해 더 짧아지는 값이 없을 때 멈춘다. 느린 섬 풀이는 땅을 각각 하나의 집합으로 만든 뒤 서로 인접한 집합을 합친다. 빠른 풀이와 구조가 다른 기준 풀이를 두면 같은 실수를 함께 저지를 가능성을 줄일 수 있다.

import io
from collections import deque
from itertools import product


DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))


def read_grid(text):
    stream = io.StringIO(text)
    rows, cols = map(int, stream.readline().split())
    grid = []
    for _ in range(rows):
        line = stream.readline().strip()
        grid.append([int(ch) for ch in line])
    if rows < 1 or cols < 1:
        raise ValueError("격자 크기는 양수여야 한다")
    if any(len(row) != cols for row in grid):
        raise ValueError("행 길이가 맞지 않는다")
    if any(cell not in (0, 1) for row in grid for cell in row):
        raise ValueError("칸 값은 0 또는 1이어야 한다")
    return grid


def maze_bfs(grid):
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] == 0 or grid[-1][-1] == 0:
        return -1

    distance = [[-1] * cols for _ in range(rows)]
    distance[0][0] = 0
    queue = deque([(0, 0)])

    while queue:
        r, c = queue.popleft()
        if (r, c) == (rows - 1, cols - 1):
            return distance[r][c]

        for dr, dc in DIRECTIONS:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            if grid[nr][nc] == 0 or distance[nr][nc] != -1:
                continue
            distance[nr][nc] = distance[r][c] + 1
            queue.append((nr, nc))

    return -1


def count_islands_dfs(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0 or seen[r][c]:
                continue
            count += 1
            seen[r][c] = True
            stack = [(r, c)]

            while stack:
                cr, cc = stack.pop()
                for dr, dc in DIRECTIONS:
                    nr, nc = cr + dr, cc + dc
                    if not (0 <= nr < rows and 0 <= nc < cols):
                        continue
                    if grid[nr][nc] == 0 or seen[nr][nc]:
                        continue
                    seen[nr][nc] = True
                    stack.append((nr, nc))

    return count


def count_islands_recursive(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]

    def visit(r, c):
        seen[r][c] = True
        for dr, dc in DIRECTIONS:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            if grid[nr][nc] == 1 and not seen[nr][nc]:
                visit(nr, nc)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and not seen[r][c]:
                count += 1
                visit(r, c)
    return count


def maze_slow(grid):
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] == 0 or grid[-1][-1] == 0:
        return -1

    infinity = rows * cols + 1
    distance = [[infinity] * cols for _ in range(rows)]
    distance[0][0] = 0

    while True:
        updated = False
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0 or distance[r][c] == infinity:
                    continue
                for dr, dc in DIRECTIONS:
                    nr, nc = r + dr, c + dc
                    if not (0 <= nr < rows and 0 <= nc < cols):
                        continue
                    if grid[nr][nc] == 0:
                        continue
                    candidate = distance[r][c] + 1
                    if candidate < distance[nr][nc]:
                        distance[nr][nc] = candidate
                        updated = True
        if not updated:
            break

    answer = distance[-1][-1]
    return -1 if answer == infinity else answer


def count_islands_slow(grid):
    groups = []
    for r, row in enumerate(grid):
        for c, cell in enumerate(row):
            if cell == 1:
                groups.append({(r, c)})

    while True:
        merged = False
        for i in range(len(groups)):
            for j in range(i + 1, len(groups)):
                touching = any(
                    abs(ar - br) + abs(ac - bc) == 1
                    for ar, ac in groups[i]
                    for br, bc in groups[j]
                )
                if touching:
                    groups[i].update(groups[j])
                    groups.pop(j)
                    merged = True
                    break
            if merged:
                break
        if not merged:
            return len(groups)


def verify_all_small():
    maze_cases = 0
    island_cases = 0

    for rows, cols in ((1, 1), (1, 3), (2, 3)):
        for cells in product((0, 1), repeat=rows * cols):
            grid = [
                list(cells[r * cols:(r + 1) * cols])
                for r in range(rows)
            ]

            fast_distance = maze_bfs(grid)
            slow_distance = maze_slow(grid)
            if fast_distance != slow_distance:
                raise AssertionError(("미로 불일치", grid))
            maze_cases += 1

            fast_count = count_islands_dfs(grid)
            recursive_count = count_islands_recursive(grid)
            slow_count = count_islands_slow(grid)
            if fast_count != slow_count or recursive_count != slow_count:
                raise AssertionError(("섬 불일치", grid))
            island_cases += 1

    return maze_cases, island_cases


def main():
    maze_text = """4 5
11001
01101
00111
00011
"""
    island_text = """4 5
11001
01001
00110
00100
"""
    maze = read_grid(maze_text)
    land = read_grid(island_text)

    print(f"미로 최단 이동 횟수: {maze_bfs(maze)}")
    print(f"섬 개수: {count_islands_dfs(land)}")

    maze_cases, island_cases = verify_all_small()
    print(f"미로 전수 대조: {maze_cases}개 통과")
    print(f"섬 전수 대조: {island_cases}개 통과")


if __name__ == "__main__":
    main()

줄별 해설

입력과 방향을 준비하는 줄

import io는 문자열을 입력 스트림처럼 읽기 위해 사용한다. deque는 큐의 앞에서 원소를 꺼내는 데 사용하고, product는 작은 격자의 모든 0과 1 배치를 만든다. 표준 라이브러리만 사용하므로 별도 설치가 필요 없다. 난수를 사용하지 않아 실행할 때마다 같은 입력을 같은 순서로 검사한다.

DIRECTIONS는 좌표 변화 네 개를 담는다. 행 번호가 위에서 아래로 증가하므로 위쪽은 (-1, 0)이고 아래쪽은 (1, 0)이다. 방향을 한곳에 모아 두면 미로와 섬에서 같은 이동 규칙을 사용한다. 느린 섬 풀이는 이 상수를 쓰지 않고 좌표 차이로 인접 여부를 판단하므로 방향 정의를 별도로 대조하는 효과도 있다.

read_grid의 stream.readline()은 실제 표준 입력에서 한 줄을 읽는 코드와 같은 형태다. 첫 줄은 split()으로 나누지만 격자 행은 문자 하나씩 정수로 바꾼다. 이 형식에서 11001은 다섯 칸이지 정수 하나가 아니다. 뒤의 검사 줄은 크기와 행 길이, 칸 값이 약속과 맞는지 확인한다. 탐색 함수 자체는 이 약속을 만족하는 비어 있지 않은 격자를 받는다.

BFS에서 거리를 기록하는 줄

maze_bfs의 첫 조건은 막힌 출발점과 도착점을 걸러 낸다. distance를 만드는 리스트 컴프리헨션은 행마다 새 리스트를 만든다. distance[0][0] = 0은 출발점의 방문 표시와 거리 설정을 동시에 수행한다. 이어서 큐에 출발점 하나를 넣는다.

queue.popleft()는 가장 먼저 등록한 칸을 꺼낸다. 꺼낸 칸이 도착점이면 저장된 거리를 반환한다. 이 검사는 이웃을 살피기 전에 있으므로 1행 1열의 열린 격자에서도 곧바로 0을 반환한다.

nr, nc를 계산한 다음에는 범위를 먼저 검사한다. Python에서 음수 인덱스는 뒤쪽 원소를 가리키므로, 배열을 읽은 뒤 범위를 확인하면 의도와 다른 칸을 볼 수 있다. 범위 안이라도 벽이거나 이미 발견한 칸이면 continue로 넘어간다. 나머지 칸에는 거리부터 기록하고 큐에 넣는다. 큐가 빌 때까지 도착점을 꺼내지 못했다면 도달할 수 없으므로 -1을 반환한다.

섬 하나를 끝까지 처리하는 줄

count_islands_dfs의 이중 반복문은 탐색을 시작할 후보를 찾는다. count += 1은 스택에서 칸을 꺼낼 때마다 실행하는 문장이 아니다. 아직 방문하지 않은 땅에서 새 탐색을 시작할 때만 실행한다. 이 위치가 섬 개수와 땅 개수를 구분한다.

시작 칸을 먼저 표시하고 스택에 넣는다. while stack 안에서는 현재 칸의 이웃 중 아직 표시하지 않은 땅만 등록한다. 스택이 비면 그 시작점과 이어진 땅을 모두 확인한 상태이므로 바깥의 칸 검사로 돌아간다. seen을 매번 새로 만들지 않고 함수 전체에서 공유해야 같은 섬을 다시 세지 않는다.

재귀 버전의 visit은 호출되자마자 현재 칸을 표시한다. 유효한 이웃이면서 아직 방문하지 않은 땅일 때만 다음 호출을 한다. 유효하지 않은 좌표로 호출한 뒤 함수 안에서 검사하는 방식과 달리, 이 코드에서는 호출 전에 조건을 확인한다. 재귀 호출이 끝나는 조건은 더 방문할 이웃이 없는 상태다.

느린 정답과 전수 대조를 만드는 줄

maze_slow의 infinity는 가능한 최단 거리보다 큰 정수다. 최단 경로에 같은 칸이 두 번 등장한다면 그 사이의 순환을 제거해 더 짧게 만들 수 있다. 따라서 열린 칸이 최대 RC개일 때 최단 이동 횟수는 RC - 1 이하이고, RC + 1은 미도달 표시로 충분하다.

느린 풀이는 시작점에서 실제로 이어지는 경로의 길이만 거리 후보로 기록한다. 더 짧은 후보가 있으면 값을 낮추고, 한 바퀴 동안 바뀐 값이 없으면 끝낸다. 종료 시 모든 인접 칸에 대해 더 줄일 수 있는 거리가 없다. 시작점에서 경로를 한 간선씩 따라 생각하면 그 경로 길이 이하의 값이 전달되어야 하므로 최단 거리와 같아진다. 도달 가능한 거리는 정수로 줄어들고 도달하지 못한 칸은 그대로 남으므로 반복도 끝난다.

count_islands_slow는 처음에 땅 하나마다 집합 하나를 만든다. 두 좌표의 행 차이 절댓값과 열 차이 절댓값의 합이 1이면 상하좌우로 이웃이다. 서로 이웃인 칸을 가진 두 집합을 합친 뒤에는 반복을 처음부터 다시 시작한다. 리스트에서 집합 하나를 제거했으므로 이전 인덱스로 계속 검사하지 않기 위한 처리다. 각 집합은 연결된 땅으로 유지되고, 더 합칠 수 없을 때 남은 집합들이 섬이다.

전수 대조의 product((0, 1), repeat=rows * cols)는 각 칸에 0 또는 1을 놓는 모든 경우를 만든다. 검사 크기는 1행 1열, 1행 3열, 2행 3열이다. 각각 2개, 8개, 64개이므로 총 74개다. 각 격자에서 미로의 두 답과 섬의 세 답을 비교한다. 불일치하면 해당 격자를 포함한 오류를 즉시 발생시킨다.

느린 미로 풀이는 최악에 전체 칸을 여러 차례 훑어 O((RC)²) 시간이 들 수 있다. 느린 섬 풀이는 집합 쌍과 좌표 쌍을 반복 확인하므로 땅 개수를 L이라 할 때 거칠게 O(L⁴)의 상한을 둘 수 있다. 둘 다 큰 입력을 처리할 목적이 아니다. 작은 범위의 모든 입력을 독립적인 방식으로 대조할 수 있다는 점이 중요하다.

전수 대조에는 전부 벽인 격자, 전부 열린 격자, 출발점만 열린 격자, 대각선으로만 닿은 땅이 자동으로 포함된다. 다만 작은 입력을 모두 통과했다는 사실이 임의 크기에 대한 증명을 대신하지는 않는다. 앞에서 세운 불변식과 함께 사용해야 한다. 마지막 main은 예시 두 개를 출력하고 대조 결과를 출력한 뒤 종료한다.

실행 결과

Python 3.12 이상인 환경에서 다음 명령을 실행한다. 첫 명령은 문법 검사를 하고, 두 번째 명령은 프로그램을 실행한다. 문법 검사에 성공하면 별도 출력이 없다.

python3 -m py_compile main.py
python3 main.py

예상 출력은 다음과 같다.

미로 최단 이동 횟수: 7
섬 개수: 3
미로 전수 대조: 74개 통과
섬 전수 대조: 74개 통과

미로에서는 (0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4) 순서로 이동할 수 있다. 칸은 여덟 개지만 이동은 일곱 번이다. 다른 최단 경로가 있어도 최소 이동 횟수는 같다. 섬 예시에서는 왼쪽 위의 세 칸, 오른쪽 위의 두 칸, 아래쪽의 세 칸이 각각 하나의 묶음이다.

실무에서 자주 틀리는 것

꺼낼 때까지 방문 표시를 미룬다

다음 코드는 이미 큐에 들어간 칸도 아직 발견하지 않은 것으로 취급한다. 여러 칸이 같은 이웃을 가리키면 중복 등록되고, 거리 값까지 다시 쓰면 처음 발견한 최단 거리도 잃을 수 있다. 조건을 보완해 동작하게 만들 수도 있지만, 이 장의 구현에서는 등록 시점에 표시하는 편이 명확하다.

# 틀린 코드: 현재 칸을 꺼낸 뒤에야 발견했다고 기록한다.
r, c = queue.popleft()
seen[r][c] = True
for nr, nc in valid_neighbors:
    if not seen[nr][nc]:
        distance[nr][nc] = distance[r][c] + 1
        queue.append((nr, nc))

# 고친 코드: 시작점도 등록 전에 표시한다.
seen[0][0] = True
queue = deque([(0, 0)])

# 이웃을 등록할 때도 같은 규칙을 적용한다.
for nr, nc in valid_neighbors:
    if not seen[nr][nc]:
        seen[nr][nc] = True
        distance[nr][nc] = distance[r][c] + 1
        queue.append((nr, nc))

위 조각의 valid_neighbors는 범위 안의 열린 이웃을 뜻한다. 완성 코드에서는 BFS의 거리 배열이 방문 표시까지 맡으므로 별도의 seen 없이 같은 원칙을 적용한다.

방문 배열의 행을 같은 리스트로 만든다

리스트를 곱하면 내부 리스트까지 복제되는 것은 아니다. 아래의 틀린 코드는 모든 행이 같은 리스트를 가리킨다. 한 칸에 표시했는데 다른 행의 같은 열까지 바뀌는 현상이 생긴다.

# 틀린 코드
seen = [[False] * cols] * rows
seen[0][0] = True

# 고친 코드
seen = [[False] * cols for _ in range(rows)]
seen[0][0] = True

거리 배열도 같은 주의가 필요하다. 행마다 독립적인 리스트를 만들어야 각 좌표의 값을 따로 보관할 수 있다.

음수 좌표를 읽은 뒤 범위를 검사한다

아래 코드에서는 nr이 -1이어도 grid[nr][nc]가 마지막 행을 읽는다. 다른 방향에서는 범위를 벗어난 인덱스로 오류가 날 수도 있다. 조건은 왼쪽부터 평가되므로 범위 검사를 앞에 둔다.

# 틀린 코드
if grid[nr][nc] == 1 and 0 <= nr < rows and 0 <= nc < cols:
    stack.append((nr, nc))

# 고친 코드
if 0 <= nr < rows and 0 <= nc < cols:
    if grid[nr][nc] == 1 and not seen[nr][nc]:
        seen[nr][nc] = True
        stack.append((nr, nc))

첫 땅에서 한 번만 탐색하고 섬 세기를 끝낸다

한 번의 탐색으로 확인하는 것은 시작점이 속한 연결 요소뿐이다. 멀리 떨어진 섬은 스스로 발견되지 않는다. 모든 칸을 검사하면서 새로 시작한 횟수를 세어야 한다.

# 틀린 코드: 다른 섬이 있어도 1만 반환한다.
visit(first_r, first_c)
return 1

# 고친 코드: visit은 연결된 땅 전체에 방문 표시한다.
count = 0
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == 1 and not seen[r][c]:
            count += 1
            visit(r, c)
return count

혼자 있는 땅도 탐색을 한 번 시작하므로 섬 하나로 센다. 땅이 전혀 없으면 탐색을 시작하지 않아 답이 0이다. 연락망의 고립된 정점도 같은 원리로 연결 요소 하나가 된다.

한눈에 보기

질문에 따라 탐색 방법과 상태를 고른다

질문	방법	핵심 상태	주의점
어디와 직접 연결되는가	인접 리스트	정점별 이웃	무방향 관계는 양쪽에 기록한다
같은 비용으로 몇 번 이동하는가	BFS	큐와 거리 배열	시작 거리와 미도달 값을 구분한다
연결된 곳을 모두 방문하는가	반복 DFS	스택과 방문 배열	스택에 넣을 때 표시한다
연결을 재귀로 따라가는가	재귀 DFS	방문 배열과 호출 스택	긴 경로에서 호출 깊이가 커진다
분리된 묶음이 몇 개인가	전체 검사와 반복 탐색	공유 방문 배열과 개수	새 탐색을 시작할 때만 센다

인접 리스트 그래프의 전체 탐색은 O(V + E), 상하좌우 격자의 전체 탐색은 O(RC)다. BFS와 DFS 중 어느 것이 더 빠르다고 외우기보다, 답을 얻기 위해 필요한 처리 순서를 먼저 판단한다. 같은 비용의 최단 거리에는 가까운 순서를 보장하는 큐가 필요하고, 연결된 묶음을 확인하는 데에는 큐와 스택 모두 사용할 수 있다.

연습 문제

1. 미로의 첫째 행이 1111, 둘째 행이 0001, 셋째 행이 1111이다. 왼쪽 위에서 오른쪽 아래까지의 최소 이동 횟수를 구하라. BFS에서 시작점의 거리를 1로 두면 이 문제의 출력 기준과 어떤 차이가 생기는지도 설명하라.
2. 보관 구역의 각 행이 차례로 1001, 0110, 1001이다. 상하좌우만 연결할 때 섬 개수를 구하라. 이어서 대각선도 연결한다고 규칙을 바꾸면 몇 개가 되는지 구하고, 코드에서 바꿀 부분을 설명하라.
3. 연락망에 P와 Q, Q와 R, S와 T의 양방향 관계가 있고 U는 이웃이 없다. 인접 리스트를 작성하고 연결 요소 개수를 구하라. 방문 표시를 각 탐색 안에서 새로 만들면 개수 세기가 왜 잘못될 수 있는지 설명하라.
4. 미로에서 최단 이동 횟수와 함께 실제 경로 하나를 반환하도록 maze_bfs를 바꾸려 한다. 처음 발견한 이웃에 어떤 정보를 추가로 저장해야 하는지, 도착 후 어떤 순서로 경로를 복원할지 설명하라. 출발점과 도착점이 같은 경우도 포함하라.

정답과 해설

1. 답은 5다. 좌표로는 (0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3)을 따라간다. 행을 두 번, 열을 세 번 바꿔야 하므로 어떤 경로도 다섯 번보다 짧을 수 없고, 실제로 다섯 번에 도달하므로 최단이다. 시작 거리를 1로 두고 그대로 출력하면 6이 되어 이동 횟수가 아니라 경로의 칸 수를 세게 된다.

2. 상하좌우 기준으로는 5개다. 가운데 행의 두 땅만 하나로 이어지고 네 모서리의 땅은 각각 떨어져 있다. 대각선을 허용하면 네 모서리가 가운데 묶음과 연결되어 1개다. 방향 목록에 (-1, -1), (-1, 1), (1, -1), (1, 1)을 추가하면 된다. 전수 대조도 유지하려면 느린 섬 풀이의 인접 조건을 함께 바꿔야 한다. 서로 다른 두 칸에 대해 행 차이와 열 차이의 절댓값 중 큰 값이 1이면 여덟 방향 이웃이다.

3. 인접 리스트는 아래와 같다. 연결 요소는 {P, Q, R}, {S, T}, {U}의 3개다. 방문 집합을 탐색마다 새로 만들면 이전 묶음의 방문 기록을 잃어 Q나 R에서도 다시 탐색을 시작할 수 있다. 전체 정점 반복문이 끝날 때까지 같은 방문 집합을 유지해야 한다.

   graph = {
       "P": ["Q"],
       "Q": ["P", "R"],
       "R": ["Q"],
       "S": ["T"],
       "T": ["S"],
       "U": [],
   }

4. 각 칸을 처음 발견할 때 바로 앞 칸의 좌표를 부모 배열에 저장한다. 이웃 (nr, nc)를 현재 칸 (r, c)에서 발견했다면 parent[nr][nc] = (r, c)로 기록한다. 도착점에서 부모를 따라 출발점까지 거슬러 올라간 뒤 모은 좌표를 뒤집으면 시작부터 도착까지의 경로가 된다. BFS가 처음 발견한 관계이므로 복원한 경로도 최단이다. 시작점의 부모는 None으로 두면 반복 종료 기준으로 쓸 수 있다. 시작과 도착이 같고 열린 칸이면 경로는 시작 좌표 하나이고 이동 횟수는 0이다. 도착할 수 없다면 거리 -1과 빈 경로를 반환하도록 약속하면 된다.