큐와 너비 우선 탐색 BFS

스택과 깊이 우선 탐색 DFS에서 DFS가 찾은 길은 가장 짧은 길이 아니었습니다. 간선 하나로 바로 갈 수 있는 정점을 세 간선을 돌아서 찾기도 했습니다. 지하철에서 가장 적은 역을 거쳐 가는 길이나, 미로에서 가장 적은 걸음으로 출구에 닿는 길을 찾으려면 다른 순서로 탐색해야 합니다. 시작 정점에서 간선 하나로 닿는 정점을 모두 먼저 보고, 그다음 간선 둘로 닿는 정점을 보는 식으로 가까운 곳부터 넓혀 가는 방법을 너비 우선 탐색(breadth-first search, BFS)이라고 합니다. 이 글에서는 큐로 BFS를 만들고, BFS가 찾은 길이 왜 가장 적은 간선을 쓰는 길인지 설명합니다.

가까운 정점부터 넓혀 간다

시작 정점에서 어떤 정점까지 가는 길 가운데 간선을 가장 적게 쓰는 길의 간선 수를 그 정점까지의 거리라고 하겠습니다. 시작 정점의 거리는 0이고, 시작 정점의 이웃은 거리 1입니다. 거리 1인 정점들의 이웃 가운데 아직 발견하지 않은 정점은 거리 2입니다. BFS는 이렇게 거리가 같은 정점들을 한 층으로 보고, 층을 하나씩 바깥으로 넓혀 가며 정점을 발견합니다.

이 순서를 지키려면 먼저 발견한 정점을 먼저 처리해야 합니다. 거리 1인 정점들을 발견한 순서대로 처리해야, 그들의 이웃인 거리 2인 정점들이 모두 그 뒤에 처리되기 때문입니다. 그래서 BFS는 먼저 넣은 것을 먼저 꺼내는 큐(queue)를 씁니다. 간선 A—B, A—C, B—D, C—D인 그래프에서 A부터 탐색하는 과정은 다음과 같습니다.

B를 처리할 때 D를 거리 2로 발견하고 B를 D의 부모로 기록합니다. C를 처리할 때도 D가 이웃이지만, 이미 발견한 정점이므로 다시 넣지 않습니다. 그래서 A에서 D까지의 길은 부모를 거슬러 올라간 A, B, D입니다. A, C, D도 똑같이 간선 두 개짜리 가장 짧은 길이지만, BFS는 이웃 목록에서 먼저 나온 B를 통해 먼저 발견한 길을 기록합니다.

큐는 deque로 만든다

Python 리스트로도 큐를 흉내 낼 수 있지만, 맨 앞을 꺼내는 pop(0)은 리스트·배열·문자열·딕셔너리의 역할에서 본 것처럼 나머지 원소를 모두 한 칸씩 당겨야 해서 O(n)이 듭니다. 표준 라이브러리 collections의 deque는 양쪽 끝에서 넣고 꺼내는 일을 모두 O(1)에 하도록 만든 자료구조라서 큐로 쓰기에 알맞습니다. append로 뒤에 넣고 popleft로 앞에서 꺼냅니다.

아래 코드는 BFS로 각 정점의 거리와 부모를 구하고, 부모 기록으로 경로를 복원합니다.

from collections import deque


def bfs(graph, start):
    distance, parent = {start: 0}, {start: None}
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                parent[neighbor] = vertex
                queue.append(neighbor)
    return distance, parent


def restore_path(parent, target):
    if target not in parent:
        return []
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]


graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"], "E": []}
distance, parent = bfs(graph, "A")
print(distance)
print(restore_path(parent, "D"), restore_path(parent, "C"), restore_path(parent, "E"))

{'A': 0, 'B': 1, 'C': 1, 'D': 2}
['A', 'B', 'D'] ['A', 'C'] []

DFS가 간선 세 개로 찾았던 C까지의 길이 BFS에서는 간선 하나인 A, C로 나옵니다. distance에 없는 정점은 시작 정점에서 닿을 수 없는 정점이라서, E까지의 경로는 빈 리스트입니다.

이 코드는 정점을 큐에 넣는 순간, 곧 처음 발견했을 때 거리와 부모를 기록합니다. distance가 방문 집합의 역할을 함께 맡아서, 이미 발견한 정점은 다시 큐에 넣지 않습니다. 발견할 때 기록해야 부모도 처음 발견한 정점으로 정해지고, 같은 정점이 큐에 두 번 들어가지 않습니다. 꺼낼 때 기록하면 어떻게 되는지는 연습 문제 2에서 확인합니다.

왜 가장 짧은 길인가

BFS가 기록한 거리가 정말 가장 짧은 거리라는 것은 큐에 정점이 들어가는 순서로 설명할 수 있습니다. 시작 정점에서 거리 d인 정점들을 처리하는 동안 새로 발견되는 정점에는 d + 1이 기록되고, 이들은 모두 큐의 뒤쪽에 들어갑니다. 그래서 큐에는 늘 거리가 d인 정점들이 앞에, d + 1인 정점들이 뒤에 있으며, 거리 d인 정점을 모두 꺼내기 전에는 거리 d + 1인 정점을 꺼내지 않습니다. 정점은 기록된 거리의 순서대로 처리되는 것입니다.

이제 어떤 정점 v의 실제 가장 짧은 거리가 k라고 합시다. 시작 정점에서 v까지 간선 k개로 가는 길을 생각하면, 그 길에서 v 바로 앞의 정점 u는 거리 k - 1입니다. u가 처리될 때 v가 아직 발견되지 않았다면 v는 k로 기록됩니다. v가 그보다 먼저 발견되었다면, v는 u보다 먼저 처리된 정점, 곧 기록된 거리가 k - 1 이하인 정점에서 발견된 것이므로 k 이하로 기록되었습니다. 그런데 기록된 거리는 실제로 그만큼의 간선으로 가는 길이 있다는 뜻이므로 실제 가장 짧은 거리 k보다 작을 수 없습니다. 따라서 기록된 거리는 정확히 k입니다. 이 성질은 시작 정점과 가까운 정점부터 차례로 성립하므로 모든 정점에서 맞습니다.

경로 복원도 이 성질 덕분에 맞습니다. v의 부모는 v를 발견한 정점이고 그 거리는 v보다 1 작습니다. 부모를 따라 거슬러 올라갈 때마다 거리가 1씩 줄어 거리 0인 시작 정점에서 멈추므로, 복원한 경로는 간선이 정확히 거리만큼인 가장 짧은 길입니다.

격자 미로의 최단 경로

BFS는 격자 모양의 미로에서 출발점부터 도착점까지 가장 적게 걷는 길을 찾을 때 자주 쓰입니다. 칸 하나를 정점으로 보고, 위·아래·왼쪽·오른쪽으로 붙어 있는 지나갈 수 있는 칸끼리 간선이 있다고 생각하면 됩니다. 이웃을 그때그때 계산할 수 있으므로 인접 목록을 미리 만들 필요가 없습니다. 아래 미로에서 #은 벽이고, S에서 G까지 가는 가장 짧은 길을 찾아 *로 표시합니다.

from collections import deque


def grid_path(rows, start, goal):
    height, width = len(rows), len(rows[0])
    parent = {start: None}
    queue = deque([start])
    while queue:
        r, c = queue.popleft()
        if (r, c) == goal:
            break
        for nr, nc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
            if 0 <= nr < height and 0 <= nc < width and rows[nr][nc] != "#" and (nr, nc) not in parent:
                parent[(nr, nc)] = (r, c)
                queue.append((nr, nc))
    if goal not in parent:
        return None
    path = []
    cell = goal
    while cell is not None:
        path.append(cell)
        cell = parent[cell]
    return path[::-1]


maze = ["S.#.",
        "..#.",
        ".#..",
        "...G"]
path = grid_path(maze, (0, 0), (3, 3))
print(len(path) - 1, "걸음")
drawing = [list(row) for row in maze]
for r, c in path[1:-1]:
    drawing[r][c] = "*"
for row in drawing:
    print("".join(row))

6 걸음
S.#.
*.#.
*#..
***G

칸은 (행, 열) 튜플로 나타내며, 튜플은 딕셔너리의 키로 쓸 수 있습니다. 이웃 후보 네 칸 가운데 격자 밖이거나 벽이거나 이미 발견한 칸은 건너뜁니다. 도착점을 꺼내면 그 거리는 이미 정해졌으므로 break로 탐색을 일찍 끝냅니다. 경로의 칸 수에서 1을 빼면 걸음 수이고, 출발점과 도착점을 뺀 칸에 *를 그렸습니다. 오른쪽 위의 두 빈칸은 G보다 멀리 있어서, G를 꺼내는 순간 탐색을 멈춘 이 코드에서는 끝내 발견되지 않습니다.

비용

각 정점은 큐에 많아야 한 번 들어가고 한 번 나오며, 꺼낼 때 그 이웃 목록을 한 번 훑습니다. 그래서 인접 목록으로 표현한 그래프에서 BFS의 시간은 DFS와 같은 O(V + E)이고, 거리와 부모와 큐는 O(V)의 공간을 씁니다. 격자 미로에서는 칸 수가 V이고 칸마다 이웃이 많아야 넷이므로 E도 O(V)이며, 전체가 칸 수에 비례합니다. 경로 복원은 경로의 길이에 비례합니다.

BFS가 다루지 못하는 것: 간선의 비용

BFS가 찾는 것은 간선의 개수가 가장 적은 길입니다. 모든 간선의 비용이 같다면 이것이 곧 비용이 가장 적은 길이지만, 간선마다 비용이 다르면 그렇지 않습니다. A에서 C로 바로 가는 간선의 비용이 100이고, A→B와 B→C의 비용이 각각 1이라면, BFS는 간선 하나짜리 A→C를 고르지만 비용은 A→B→C의 2가 훨씬 적습니다. 비용의 합이 가장 적은 길은 다음 장의 Dijkstra·완화·오래된 큐 항목에서 큐 대신 우선순위 큐를 써서 찾습니다.

정리

• BFS는 큐를 써서 먼저 발견한 정점부터 처리하므로, 시작 정점에서 거리가 0, 1, 2인 정점들을 층별로 차례로 발견합니다.
• 큐는 양쪽 끝을 O(1)에 다루는 collections.deque로 만들고, append로 넣고 popleft로 꺼냅니다.
• 정점을 처음 발견할 때 거리와 부모를 기록하면, 같은 정점이 큐에 두 번 들어가지 않고 부모는 처음 발견한 정점이 됩니다.
• 큐에는 거리가 작은 정점이 앞에 있으므로, 처음 기록한 거리가 가장 짧은 거리이고 부모를 따라 복원한 경로가 가장 적은 간선을 쓰는 길입니다.
• BFS는 O(V + E)이며 격자 미로처럼 이웃을 계산할 수 있는 문제에도 쓰지만, 간선마다 비용이 다르면 비용이 가장 적은 길을 찾지 못합니다.

연습 문제

1. 간선을 하나 더하면

본문 그래프에 간선 A—D를 더하면 A에서 시작한 BFS에서 D의 거리와 부모, A에서 D까지의 경로는 어떻게 될까요?

2. 꺼낼 때 방문을 표시하면

distance에 기록하는 일을 정점을 큐에서 꺼낼 때로 미루면, 본문 그래프에서 A부터 탐색할 때 큐에 정점이 모두 몇 번 들어갈까요?

3. 길이 없는 미로

본문의 미로에서 맨 아래 줄을 ".#.G"로 바꾸면 grid_path는 무엇을 돌려줄까요?

다음 장의 Dijkstra·완화·오래된 큐 항목에서는 간선마다 비용이 다른 그래프에서 비용의 합이 가장 적은 길을 찾습니다. 모든 정점 쌍 사이에 길이 있는지를 한꺼번에 구하는 방법은 Warshall과 도달 가능성의 논리에서 다룹니다.