그래프 탐색 BFS와 DFS, 큐와 스택으로 갈리는 선택 기준
그래프는 정점과 간선으로 이뤄진 자료구조이고, BFS는 큐로 가까운 정점부터, DFS는 스택·재귀로 깊이 먼저 훑는다. 가중치 없는 최단 경로는 BFS, 완전 탐색·사이클 추적은 DFS를 쓴다. 파이썬 예제로 둘의 차이와 선택 기준을 정리했다.
그래프 탐색은 정점과 간선으로 이어진 그래프를 하나씩 훑는 작업이고, 그 대표 방법이 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이다. 한 줄로 요약하면 BFS는 큐를 써서 출발점에서 가까운 정점부터 넓게 퍼져 나가고, DFS는 스택이나 재귀로 한 갈래를 끝까지 파고든다. 그래서 가중치가 없는 그래프에서 간선을 가장 적게 거치는 최단 경로를 찾을 때는 BFS를, 모든 정점을 훑거나 사이클과 경로를 추적할 때는 DFS를 고른다. 이 글은 가중치가 없는 그래프를 기준으로 두 탐색의 차이와 선택 기준, 파이썬 구현만 다룬다. 간선마다 비용이 다른 그래프의 최단 경로(다익스트라 알고리즘 등)는 범위를 벗어나므로 여기서는 짚지 않는다. 큐 구현은 파이썬 공식 문서가 권장하는 collections.deque를 쓴다.
그래프를 코드로 옮기는 흔한 방법, 인접 리스트
그래프는 정점(vertex, 데이터를 담는 점)과 그 정점들을 잇는 간선(edge, 연결선)으로 이루어진 자료구조다. 코드로 옮길 때 가장 많이 쓰는 방식은 인접 리스트다. 정점마다 '나와 직접 이어진 이웃 정점의 목록'을 들고 있는 구조로, 파이썬에서는 딕셔너리와 리스트만으로 충분히 표현한다.
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2],
}이렇게 두면 graph[0]으로 0번 정점의 이웃인 1과 2를 바로 꺼낼 수 있다. 정점 수를 V, 간선 수를 E라고 할 때 인접 리스트는 실제로 존재하는 간선만 저장한다. 그래서 이웃이 몇 개뿐인 성긴 그래프에서 메모리를 아끼고, 한 정점의 이웃을 훑는 비용도 그 정점에 붙은 간선 수만큼만 든다. 정점을 목록으로 이어 두는 이 발상은 노드를 포인터로 잇는 연결 리스트 자료구조와 뿌리가 닮았다.
BFS와 DFS는 무엇이 다른가?
둘의 차이는 '다음에 방문할 정점을 어디에 쌓아 두느냐' 하나로 갈린다. BFS는 큐에, DFS는 스택(또는 재귀 호출)에 쌓는다.
BFS는 먼저 넣은 것을 먼저 꺼내는 큐(FIFO)에 이웃을 담아 앞에서부터 꺼낸다. 그래서 출발점에서 한 칸 거리인 정점을 모두 본 다음 두 칸 거리로 넘어가는 식으로, 가까운 곳부터 층층이 넓게 퍼진다. 반대로 DFS는 나중에 넣은 것을 먼저 꺼내는 스택(LIFO)이나 재귀를 써서 한 갈래를 막힐 때까지 파고든 뒤 되돌아 나온다. 이 큐와 스택의 성질이 두 탐색의 성격을 그대로 정하는데, FIFO와 LIFO가 어떻게 다른지는 스택과 큐를 비교한 글에 자세히 풀어 두었다.
파이썬에서 BFS의 큐는 collections.deque로 만든다. 파이썬 공식 문서는 deque가 양쪽 끝에서의 추가와 삭제를 O(1)로 처리한다고 설명한다. 리스트의 pop(0)이 앞 원소를 지우며 뒤를 모두 당기느라 O(n)이 드는 것과 대비된다.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
if nxt not in visited:
visited.add(nxt)
queue.append(nxt)
return orderDFS는 재귀로 적으면 더 짧다. 방문 표시를 남기고 이웃을 하나씩 파고들면 된다.
def dfs(graph, node, visited):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs(graph, nxt, visited)두 코드 모두 이미 방문한 정점을 visited에 담아 다시 밟지 않게 막는 점이 핵심이다. 이 장치가 없으면 정점들이 서로 이어진 그래프에서 같은 곳을 무한히 맴돈다. 재귀 DFS는 한 가지 주의할 점이 있다. 파이썬은 재귀 깊이에 기본 한도가 있어 정점이 아주 길게 한 줄로 이어진 그래프에서는 명시적 스택으로 바꾸는 편이 안전하다. 성능만 보면 두 방법 모두 인접 리스트에서 정점을 한 번, 간선을 한 번씩만 훑으므로 시간 복잡도가 O(V+E)로 같다. 즉 속도로는 우열을 가리기 어렵고, 무엇을 먼저 방문하느냐만 다르다.
언제 BFS를 쓰고 언제 DFS를 쓰나?
가중치가 없는 그래프에서 '최단 거리'가 필요하면 BFS, 그렇지 않은 대부분은 DFS가 편하다. BFS는 가까운 정점부터 방문하므로 목표 정점에 처음 닿는 순간이 곧 간선을 가장 적게 거친 경로가 된다. 미로에서 최소 몇 칸을 움직여야 출구에 닿는지, 인맥 그래프에서 두 사람이 몇 다리 건너 이어지는지처럼 '최소 횟수'를 묻는 문제가 BFS의 자리다.
DFS는 한 갈래를 끝까지 밀어붙이는 성질 덕분에 완전 탐색과 잘 맞는다. 모든 정점을 빠짐없이 방문해 연결 요소가 몇 덩어리인지 세거나, 경로를 되짚어 사이클이 있는지 확인하거나, 작업 순서를 정하는 위상 정렬, 가능한 조합을 하나씩 시도하는 백트래킹이 대표적이다. 메모리 관점에서도 차이가 있다. BFS는 한 층의 정점을 모두 큐에 담기 때문에 폭이 넓게 퍼지는 그래프에서 큐가 커지고, DFS는 지금 파고든 경로의 깊이만큼만 스택을 쓴다.
실무에서는 문제 문장의 단어로 고르면 대체로 맞다. '최단 경로', '최소 이동', '가장 빠른'이라는 말이 보이면 BFS를 먼저 떠올리고, '모든 경우', '경로가 존재하는지', '순서를 정한다'는 요구가 보이면 DFS를 고른다. 둘은 경쟁 관계가 아니라 같은 그래프를 다른 순서로 훑는 두 렌즈이므로, 풀려는 문제가 거리를 묻는지 구조를 묻는지부터 가리는 것이 먼저다.
