[자료구조 14] 그래프 순회 BFS와 DFS

그래프를 딕셔너리로 담아 두었다면, 이제 그 안의 모든 노드를 빠짐없이 방문하는 방법이 필요합니다. 노드를 하나씩 찾아 훑는 것을 순회(traversal, 모든 노드를 방문하는 것)라고 합니다. 방법은 크게 두 가지입니다. 하나는 BFS(너비 우선 탐색, Breadth-First Search)로 가까운 노드부터 물결처럼 퍼져 나가고, 다른 하나는 DFS(깊이 우선 탐색, Depth-First Search)로 한 방향으로 끝까지 파고듭니다. 이번 글에서는 같은 그래프를 두 방식으로 훑으며 차이를 눈으로 확인해 보겠습니다.

먼저 아래 그래프를 공통으로 사용하겠습니다. 각 노드가 어떤 이웃과 이어져 있는지 딕셔너리로 담은 것입니다.

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

14.1 BFS: 큐로 가까운 것부터 방문하기

BFS는 시작 노드에서 가까운 이웃부터 차례로 방문합니다. 물에 돌을 던지면 파문이 동심원으로 퍼지듯이, 시작점에서 한 칸 거리의 노드를 모두 방문한 뒤 두 칸 거리로 넘어갑니다. 이 순서를 지키려면 큐(queue, 먼저 넣은 것을 먼저 꺼내는 구조)가 필요합니다. 파이썬에서는 앞에서 빼기가 빠른 collections의 deque를 씁니다.

from collections import deque
def bfs(g, start):
visited = []
seen = {start}
q = deque([start])
while q:
node = q.popleft()
visited.append(node)
for nb in g[node]:
if nb not in seen:
seen.add(nb)
q.append(nb)
return visited
print(bfs(g, "A"))

['A', 'B', 'C', 'D', 'E', 'F']

동작을 따라가 보겠습니다. 먼저 A를 큐에 넣습니다. A를 꺼내 방문하고, A의 이웃 B와 C를 큐에 넣습니다. 다음으로 B를 꺼내 방문하고 B의 이웃 중 아직 안 본 D와 E를 넣습니다. 이렇게 먼저 발견한 이웃부터 처리하기 때문에 시작점과 가까운 순서로 퍼집니다.

여기서 seen이라는 집합이 중요합니다. 이미 큐에 넣은 노드를 다시 넣지 않도록 표시하는 역할입니다. 집합의 in 검사는 평균 O(1)이라 빠릅니다. 이 표시가 없으면 서로 이웃인 A와 B를 오가며 무한히 반복하게 됩니다. BFS는 시작점에서 각 노드까지의 최단 거리(칸 수)를 찾을 때 특히 많이 쓰입니다.

복잡도는 O(노드 수 + 엣지 수)입니다. 모든 노드를 한 번씩 방문하고, 각 노드의 이웃을 한 번씩만 확인하기 때문입니다.

14.2 DFS: 재귀로 끝까지 파고들기

DFS는 반대입니다. 한 이웃을 골라 그 길로 갈 수 있는 데까지 끝까지 들어갑니다. 더 갈 곳이 없으면 되돌아 나와 다른 길을 시도합니다. 미로에서 벽을 짚고 한 방향으로 계속 가다가 막히면 돌아 나오는 것과 같습니다. 이 방식은 재귀(recursion, 함수가 자기 자신을 다시 부르는 것)로 자연스럽게 표현됩니다.

def dfs(g, start):
visited = []
seen = set()
def go(node):
seen.add(node)
visited.append(node)
for nb in g[node]:
if nb not in seen:
go(nb)
go(start)
return visited
print(dfs(g, "A"))

['A', 'B', 'D', 'E', 'F', 'C']

순서를 보겠습니다. A에서 시작해 첫 이웃 B로 들어갑니다. B에서 다시 첫 이웃 D로 들어갑니다. D는 더 갈 곳이 없으니 되돌아 나와 B의 다음 이웃 E로 갑니다. E에서 F로 들어가고, F를 지나 마지막에 C를 방문합니다. BFS가 A, B, C, D 순으로 가까운 것부터 퍼진 것과 달리, DFS는 A, B, D처럼 한 줄기를 끝까지 따라 내려간 점이 다릅니다.

go 함수가 자기 자신을 다시 부르는 것이 곧 깊이 우선입니다. 함수가 자신을 부를 때마다 파이썬이 내부적으로 "돌아올 자리"를 차곡차곡 쌓아 두는데, 이것이 바로 다음에 볼 스택입니다.

14.3 DFS를 스택으로 직접 짜기

재귀 없이도 DFS를 만들 수 있습니다. 재귀가 내부적으로 쓰던 그 쌓기 구조, 즉 스택(stack, 나중에 넣은 것을 먼저 꺼내는 구조)을 우리가 직접 리스트로 만들어 쓰면 됩니다.

def dfs_stack(g, start):
visited = []
seen = set()
st = [start]
while st:
node = st.pop()
if node in seen:
continue
seen.add(node)
visited.append(node)
for nb in reversed(g[node]):
if nb not in seen:
st.append(nb)
return visited
print(dfs_stack(g, "A"))

['A', 'B', 'D', 'E', 'F', 'C']

결과가 재귀 DFS와 똑같습니다. 리스트의 pop()은 끝에서 꺼내므로 스택처럼 동작합니다. 가장 최근에 넣은 노드를 먼저 꺼내 그 길로 파고드는 것입니다. 이웃을 넣을 때 reversed로 순서를 뒤집은 것은, 재귀판과 방문 순서를 똑같이 맞추기 위해서입니다. 재귀가 부담스러운 아주 깊은 그래프에서는 이렇게 스택으로 직접 짜기도 합니다.

DFS 역시 복잡도는 O(노드 수 + 엣지 수)입니다. 모든 노드와 엣지를 한 번씩 훑는다는 점은 BFS와 같습니다.

14.4 정리: BFS와 DFS의 차이

두 방법은 모든 노드를 방문한다는 목표는 같지만 순서가 다릅니다. BFS는 큐를 써서 가까운 노드부터 물결처럼 퍼지고, 시작점에서의 최단 거리를 구할 때 유용합니다. DFS는 스택 또는 재귀를 써서 한 방향으로 끝까지 파고들며, 모든 경로를 뒤지거나 미로 탐색 같은 문제에 어울립니다.

기억할 짝은 간단합니다. BFS는 큐(deque), DFS는 스택(리스트) 또는 재귀입니다. 순서를 결정하는 것이 바로 이 자료구조의 차이입니다. 큐는 먼저 넣은 것을 먼저 꺼내므로 가까운 이웃부터 처리되고, 스택은 나중에 넣은 것을 먼저 꺼내므로 방금 발견한 이웃으로 곧장 파고듭니다. 같은 그래프인데도 어떤 그릇에 담아 꺼내느냐에 따라 방문 순서가 갈리는 것입니다.

그리고 두 방법 모두 seen 집합으로 이미 방문한 노드를 표시해 무한 반복을 막는다는 공통점이 있습니다. 이 표시를 빠뜨리면 서로 이웃인 노드 사이를 오가며 프로그램이 멈추지 않으니 주의해야 합니다. 같은 그래프에 두 함수를 각각 돌려 보고, 방문 순서가 어떻게 갈리는지 직접 확인해 보시기 바랍니다.