BFS와 DFS — 그래프 탐색의 두 축

코딩테스트 그래프 문제의 대부분은 결국 탐색이다. 미로 최단 거리, 연결 요소 세기, 섬의 개수 — 문제 껍데기는 달라도 안에서 도는 것은 BFS(너비 우선) 아니면 DFS(깊이 우선)다. 두 탐색은 “다음에 어느 노드를 볼 것인가”를 정하는 자료구조 하나로 갈린다. BFS는 큐, DFS는 스택(또는 재귀 호출 스택)이다.

같은 그래프, 두 순서

인접 리스트로 표현한 그래프 하나에 두 탐색을 모두 돌려보자.

from collections import deque

graph = {1: [2, 3], 2: [4], 3: [4, 5], 4: [6], 5: [6], 6: []}

def bfs(start):
    visited = {start}
    q = deque([(start, 0)])            # (노드, 시작에서의 거리)
    order = []
    while q:
        node, dist = q.popleft()
        order.append((node, dist))
        for nxt in graph[node]:
            if nxt not in visited:     # 큐에 넣을 때 방문 체크
                visited.add(nxt)
                q.append((nxt, dist + 1))
    return order

def dfs(node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nxt in graph[node]:
        if nxt not in visited:
            order.extend(dfs(nxt, visited))
    return order

print(bfs(1))  # [(1, 0), (2, 1), (3, 1), (4, 2), (5, 2), (6, 3)]
print(dfs(1))  # [1, 2, 4, 6, 3, 5]

BFS는 시작점에서 가까운 층부터 한 겹씩 훑는다. 거리 0인 노드를 다 보고, 거리 1을 다 보고, 그다음 거리 2로 넘어간다. DFS는 한 갈래를 끝(6)까지 파고든 뒤에야 되돌아와 다음 갈래(3, 5)를 본다. 두 방식 모두 모든 노드·간선을 한 번씩 보므로 시간복잡도는 O(V+E)로 같다 — 다른 것은 순서다.

순서가 다르면 풀 수 있는 문제가 다르다

BFS = 최단 거리: 가까운 층부터 방문하므로, 어떤 노드에 처음 도달한 순간의 거리가 곧 최단 거리다(간선 가중치가 모두 같을 때만). 미로 탈출, 최소 이동 횟수 문제는 BFS가 정답 축이다.
DFS = 끝까지 가보기: 경로 하나를 완성해봐야 아는 문제 — 모든 경로 나열, 백트래킹(조합·순열 생성), 사이클 탐지 — 는 DFS의 영역이다.
아무거나 되는 문제: 연결 요소 개수, 방문 가능 여부처럼 “닿는가”만 물으면 둘 다 된다. 이때는 구현이 짧은 쪽을 쓰면 된다.

자주 터지는 함정 두 가지

방문 체크 시점. BFS에서 visited 체크를 큐에서 꺼낼 때 하면, 같은 노드가 여러 번 큐에 들어가 시간 초과가 난다. 위 코드처럼 넣을 때 체크해야 각 노드가 큐에 정확히 한 번 들어간다.

재귀 깊이. 파이썬의 기본 재귀 한도는 1000 안팎이라, 노드 수십만 개짜리 그래프를 재귀 DFS로 돌면 RecursionError가 난다. sys.setrecursionlimit을 올리거나, 명시적 스택을 쓰는 반복문 DFS로 바꾸면 된다 — 큐를 스택으로 바꾸면 BFS 코드가 거의 그대로 DFS가 된다.

정리

BFS와 DFS는 우열이 아니라 용도의 문제다. “최단”이라는 단어가 보이면 BFS, “모든 경우”가 보이면 DFS(백트래킹), 연결만 물으면 아무거나 — 이 감각만 잡혀도 그래프 문제의 절반은 자료구조 선택이 끝난 셈이다.