BFS와 DFS 차이는 구현 문법보다 무엇을 먼저 보장하느냐에 있습니다. 최소 이동 횟수와 무가중치 최단거리를 묻는다면 BFS, 경로 존재와 구조 분석을 묻는다면 DFS를 먼저 떠올리면 문제 선택이 훨씬 쉬워집니다.
많은 초보자가 둘 다 방문 배열을 쓰고 둘 다 그래프를 돈다는 이유로 같은 도구처럼 느낍니다. 하지만 실제 문제에서는 차이가 분명합니다. BFS는 넓게 퍼지며 거리 레벨을 보장하고, DFS는 깊게 들어가며 구조와 되돌아오는 흐름을 보여줍니다.
먼저 한 줄
- BFS는 가까운 정점부터 보므로 무가중치 최단거리에 강합니다.
- DFS는 한 경로를 끝까지 따라가므로 경로 존재 확인과 구조 탐색에 강합니다.
- 둘 다 O(V + E)일 수 있지만 먼저 얻는 정보가 다릅니다.
핵심은 속도보다 순서입니다. 둘 다 그래프 전체를 훑을 수 있지만, 무엇을 먼저 방문하느냐가 문제의 정답 조건과 맞아야 합니다.
BFS와 DFS 차이: 왜 BFS가 최단거리일까
BFS는 거리 0, 1, 2, 3 순으로 레벨을 넓혀 가는 탐색입니다. 그래서 어떤 정점을 처음 만났다는 사실 자체가 이미 그 정점까지 가는 최소 간선 수를 뜻합니다. 이 보장은 간선 가중치가 없는 그래프에서 특히 강력합니다.
미로처럼 한 칸 이동 비용이 모두 같다면 BFS는 1번 만에 갈 수 있는 칸을 모두 확인한 뒤에야 2번 만에 갈 수 있는 칸으로 넘어갑니다. 그래서 도착점을 처음 만나는 순간 그 경로는 최단거리입니다.
무가중치 그래프에서 BFS가 강한 이유는 빨라서가 아니라 첫 방문 자체가 최단거리라는 보장을 주기 때문입니다.
레벨 순서
- 거리 0: 1
- 거리 1: 2, 3
- 거리 2: 4, 5
- 거리 3: 6
정점 1에서 6까지 가는 최소 간선 수를 묻는다면, BFS는 6을 처음 만나는 순간 답을 얻습니다. 부모 배열을 함께 저장하면 실제 최단 경로도 바로 복원할 수 있습니다.
from collections import deque
def bfs_shortest_path(graph, start, target):
queue = deque([start])
visited = {start}
dist = {start: 0}
parent = {start: None}
while queue:
cur = queue.popleft()
if cur == target:
path = []
node = target
while node is not None:
path.append(node)
node = parent[node]
return dist[target], path[::-1]
for nxt in graph[cur]:
if nxt not in visited:
visited.add(nxt)
dist[nxt] = dist[cur] + 1
parent[nxt] = cur
queue.append(nxt)
return None이 코드에서 큐는 레벨 순서를 유지하기 위한 도구입니다. 진짜 핵심은 가까운 정점부터 확정한다는 규칙입니다.
왜 DFS는 경로와 구조에 강할까
DFS는 한 갈래를 잡으면 끝까지 들어갔다가, 막히면 그제야 돌아옵니다. 이 흐름은 최단거리 보장에는 불리하지만 경로 존재 확인, 백트래킹, 사이클 탐지, 연결 요소 찾기, 위상 정렬 같은 문제에는 매우 자연스럽습니다.
예를 들어 도착점까지 가는 경로가 하나라도 있는지를 묻는다면 DFS는 직관적입니다. 한 길을 끝까지 따라가 보고, 실패하면 되돌아와 다른 길을 시도하면 되기 때문입니다.
DFS의 강점은 가장 짧은 길을 먼저 찾는 데 있지 않고, 한 경로의 내부 구조를 끝까지 확인하고 되돌아오는 흐름에 있습니다.
먼저 찾은 길
예를 들어 A에서 E까지 가는 길이 있을 때, DFS가 인접 정점을 B부터 보면 A → B → D → E를 먼저 찾을 수 있습니다. 하지만 더 짧은 경로가 A → C → E라면 DFS는 그것을 먼저 보장하지 못합니다. 즉, 일반 그래프에서 DFS가 처음 찾은 경로는 정답 경로일 수는 있어도 최단 경로라고 단정할 수 없습니다.
- 경로가 존재하는지 확인
- 연결 요소 개수 세기
- 사이클 찾기
- 트리 순회
- 위상 정렬
- 진입 시간과 종료 시간 기반 구조 분석
def has_path_dfs(graph, start, target):
visited = set()
def dfs(node):
if node == target:
return True
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
if dfs(nxt):
return True
return False
return dfs(start)이 코드의 핵심은 레벨이 아니라 한 경로를 끝까지 따라가는 흐름입니다. 그래서 구조 문제일수록 DFS 쪽 감각이 잘 맞습니다.
같은 O(V + E)인데 왜 다를까
둘 다 정점과 간선을 한 번씩 볼 수 있으니 비용의 큰 틀은 비슷합니다. 하지만 BFS는 큐를 써서 가까운 정점을 먼저 확정하고, DFS는 스택 흐름이나 재귀를 써서 한 갈래를 먼저 소진합니다. 그래서 BFS는 거리 레벨을 보존하고, DFS는 탐색 트리와 되돌아오는 순서를 보존합니다.
즉, 둘은 성능 경쟁 관계가 아니라 무엇을 먼저 보장하느냐의 차이로 이해하는 편이 더 정확합니다.
문제에서 고르는 법
BFS 신호
- 최소 이동 횟수
- 가장 적은 간선 수
- 무가중치 최단거리
- 몇 단계 떨어져 있는지
- 미로에서 가장 빨리 도착하는 길
문제 문장에 최소, 가장 적게, 몇 번 만에 같은 표현이 있고 간선 가중치가 없다면 BFS를 기본값으로 두는 편이 맞습니다.
DFS 신호
- 갈 수 있는 경로가 존재하는지
- 모든 경우를 따라가며 확인해야 하는지
- 사이클이 있는지
- 연결 구조를 분해해야 하는지
- 위상 정렬이나 트리 순회처럼 깊이 우선 흐름이 자연스러운지
특히 경로 자체보다 구조의 성질을 묻는 순간 DFS 쪽 신호가 강해집니다.
헷갈리는 예외
트리라면
트리에서는 두 정점 사이 단순 경로가 하나뿐입니다. 그래서 DFS로 찾아도 결국 그 경로가 유일한 경로이고, 따라서 최단거리이기도 합니다. 하지만 이것은 트리라서 가능한 예외입니다. 일반 그래프에서는 여러 경로가 존재하므로 DFS가 먼저 찾은 경로가 가장 짧다고 볼 수 없습니다.
가중치가 있다면
간선마다 비용이 다르면 BFS의 레벨 개념이 곧 거리 개념이 되지 않습니다. 이때는 다익스트라처럼 가중치를 고려하는 알고리즘이 필요합니다. 즉, BFS는 모든 최단거리 문제의 정답이 아니라 무가중치 최단거리 문제의 정답입니다.
자주 하는 실수
- 최단거리 문제를 DFS로 풀고 모든 경로를 다 비교한다.
- BFS를 쓰면서 부모 배열을 저장하지 않아 경로 복원을 못 한다.
- 가중치 그래프인데도 BFS를 그대로 적용한다.
- DFS 재귀 깊이를 생각하지 않고 큰 입력에 바로 재귀를 쓴다.
특히 첫 번째 실수는 정답은 나와도 문제의 핵심 구조를 놓친 풀이가 되기 쉽습니다.
마무리
정답 조건이 거리면 BFS를 먼저 보고, 정답 조건이 구조면 DFS를 먼저 보는 습관을 들이면 문제 풀이가 훨씬 빨라집니다. 한 문장으로 줄이면 BFS는 가까운 것부터 확정하는 탐색이고, DFS는 한 갈래를 끝까지 파고드는 탐색입니다. 그래서 최단거리는 BFS, 경로 존재와 구조 탐색은 DFS가 기본 선택이 됩니다.
관련해서 내부 글로는 DFS와 BFS는 언제 다르게 써야 할까, 스택과 큐 차이: FIFO와 LIFO는 언제 쓰일까, 이진 탐색 트리와 해시 테이블 차이를 함께 보면 자료구조 선택 감각을 더 넓게 잡는 데 도움이 됩니다. 외부 참고로는 cp-algorithms의 BFS 문서와 DFS 문서가 기본 성질을 다시 확인하는 데 좋습니다.
