다익스트라 BFS 차이는 알고리즘 이름보다 먼저 이 문제의 거리 정의가 간선 수인지, 누적 비용인지를 구분하면 훨씬 쉽게 이해됩니다. BFS는 무가중치 그래프에서 간선 수가 가장 적은 경로를 찾고, 다익스트라는 비음수 가중치 그래프에서 총비용이 가장 작은 경로를 찾습니다.
그래서 가중치가 붙는 순간 중요한 질문은 ‘그래프냐 최단 경로냐’가 아니라, 모든 이동 비용이 같은지, 아니면 칸마다 비용이 달라지는지입니다. 이번 글에서는 BFS가 언제 충분한지, 왜 가중치가 붙으면 다익스트라가 등장하는지, 그리고 0-1 BFS까지 어디서 갈리는지 실전 기준으로 정리하겠습니다.
한 줄 기준부터 잡기
- 모든 간선의 비용이 같으면 BFS
- 간선마다 비용이 다르면 다익스트라
- 비용이 0 또는 1뿐이면 0-1 BFS도 가능
- 음수 가중치가 있으면 다익스트라를 바로 쓰면 안 된다
입문 단계에서는 이 네 줄만 먼저 잡아도 충분합니다. 특히 가중치가 붙었다는 사실 자체보다, 그 가중치가 모두 같은지 다른지가 더 중요합니다.
BFS가 보장하는 최단 경로는 무엇일까
BFS는 시작점에서 한 층씩 넓게 퍼져 나갑니다. 그래서 먼저 도달한 경로는 간선 개수가 가장 적은 경로입니다. 즉 BFS의 거리 개념은 지나간 간선 수라고 이해하면 됩니다.
- A → B
- A → C
- B → D
- C → D
위 그래프에서 A에서 D로 가는 경로는 A → B → D, A → C → D 두 가지이고 둘 다 간선 수는 2개입니다. 무가중치 그래프에서는 이 기준이 곧 최단 거리 기준이므로 BFS가 정확하게 동작합니다.
공식적으로도 BFS는 무가중치 그래프에서 시작점으로부터 각 정점까지의 최단 경로, 즉 가장 적은 간선 수의 경로를 찾는 알고리즘으로 설명됩니다.
가중치가 붙는 순간 왜 BFS가 흔들릴까
간선마다 비용이 다르면 이야기가 달라집니다. 이제 거리의 의미는 더 이상 이동 횟수가 아니라 누적 비용 합이 됩니다.
- A → B → D : 간선 2개, 총비용 101
- A → C → D : 간선 2개, 총비용 6
간선 수만 보면 두 경로는 똑같습니다. 하지만 실제 최단 비용 경로는 두 번째입니다. BFS는 레벨, 즉 간선 수를 기준으로 보기 때문에 총비용 차이를 제대로 반영하지 못합니다.
그래서 가중치가 붙는 순간 알고리즘 선택의 핵심은 바로 이것입니다. 거리 = 간선 수인지, 거리 = 누적 비용인지 먼저 확인해야 합니다.
다익스트라는 무엇을 다르게 볼까
다익스트라는 현재까지 발견된 후보 중에서 누적 비용이 가장 작은 정점을 먼저 확정해 나갑니다. BFS가 큐에 먼저 들어온 순서를 따라간다면, 다익스트라는 우선순위 큐를 사용해 현재 거리값이 가장 작은 후보를 먼저 꺼냅니다.
그리고 어떤 정점에서 다음 간선을 하나 더 탔을 때 더 싼 경로가 나오면 그 거리값을 갱신합니다. 이 과정을 보통 완화(relaxation)라고 부릅니다.
즉, 다익스트라는 ‘지금 한 단계 가까운가’보다 전체 비용 합이 더 작은가를 끝까지 추적하기 위해 등장합니다.
BFS와 다익스트라를 코드 감각으로 비교하면
BFS의 거리 갱신 감각
from collections import deque
q = deque([start])
dist[start] = 0
while q:
cur = q.popleft()
for nxt in graph[cur]:
if dist[nxt] == -1:
dist[nxt] = dist[cur] + 1
q.append(nxt)이 코드는 모든 간선 비용이 사실상 1이라고 볼 수 있을 때 잘 맞습니다. 다음 정점으로 갈 때마다 거리가 항상 1만큼만 늘어나기 때문입니다.
다익스트라의 거리 갱신 감각
import heapq
INF = 10**18
dist = [INF] * n
dist[start] = 0
pq = [(0, start)]
while pq:
cur_dist, cur = heapq.heappop(pq)
if cur_dist > dist[cur]:
continue
for nxt, weight in graph[cur]:
new_dist = cur_dist + weight
if new_dist < dist[nxt]:
dist[nxt] = new_dist
heapq.heappush(pq, (new_dist, nxt))여기서는 +1 대신 +weight가 들어갑니다. 이 차이가 바로 ‘이동 횟수 최단’과 ‘누적 비용 최단’의 차이입니다.
가중치가 붙으면 무조건 다익스트라일까
입문 설명에서는 편의를 위해 그렇게 말할 때가 많지만, 정확하게는 예외가 있습니다. 모든 가중치가 같다면 가중치 그래프라고 해도 무가중치처럼 볼 수 있으므로 BFS가 가능합니다.
모든 가중치가 같다면
모든 간선 비용이 1이라면 총비용 최소는 곧 간선 수 최소와 같습니다. 그래서 이 경우에는 BFS가 그대로 최단 경로를 구합니다.
가중치가 0 또는 1뿐이라면
이 경우는 0-1 BFS를 쓸 수 있습니다. 비용 0 간선은 deque의 앞에, 비용 1 간선은 뒤에 넣어 거리 순서를 유지하는 방식입니다. 공식 설명에서도 이런 특수한 가중치 제약에서는 일반 다익스트라보다 더 단순한 방법이 가능하다고 정리합니다.
- 모두 동일한 비용: BFS
- 비용이 0 또는 1: 0-1 BFS
- 일반적인 비음수 가중치: 다익스트라
- 음수 가중치 포함: 다른 알고리즘 검토
다익스트라가 성립하는 중요한 전제
다익스트라는 음수 가중치가 없을 때 안전합니다. 이미 최단 거리라고 확정한 정점이 나중에 음수 간선 때문에 더 짧아질 수 있다면, 알고리즘의 핵심 전제가 무너집니다.
그래서 다익스트라를 고르기 전에 가장 먼저 확인할 질문은 이것입니다. 간선 가중치가 모두 0 이상인가?
실전에서 제일 많이 헷갈리는 장면
격자 맵 이동 문제
한 칸 이동 비용이 모두 1이면 BFS가 맞습니다. 하지만 평지는 1, 늪은 3, 산길은 5처럼 칸마다 비용이 다르면 이제는 이동 횟수가 아니라 비용 합을 봐야 하므로 다익스트라가 필요합니다.
환승 횟수 최소 vs 요금 최소
정거장 수나 환승 횟수를 최소화하는 문제는 BFS 쪽 감각이고, 실제 요금 합이나 이동 시간 합을 최소화하는 문제는 다익스트라 쪽 감각입니다. 문제 문장이 무엇을 최소화하라고 요구하는지 그대로 읽는 습관이 중요합니다.
벽을 부수면 비용 1, 그냥 가면 비용 0
이런 문제는 0-1 BFS의 전형입니다. 가중치가 있긴 하지만 0 또는 1로만 제한되어 있어서, 일반 다익스트라보다 더 직접적으로 풀 수 있습니다.
빠르게 고르는 체크리스트
- 내가 최소화하려는 값이 무엇인가
- 그 값이 간선 개수와 같은 의미인가
- 간선 가중치가 모두 같은가
- 가중치가 0 또는 1뿐인가
- 가중치가 일반적인 비음수 값인가
- 음수 가중치가 섞여 있는가
이 체크리스트를 알고리즘 선택으로 바꾸면 이렇게 됩니다. 간선 수 최소라면 BFS, 동일 비용 그래프라면 BFS, 0/1 비용 그래프라면 0-1 BFS, 비음수 가중치 최단 비용이라면 다익스트라입니다.
자주 하는 오해
- BFS를 조금 고치면 다익스트라 대신 쓸 수 있다 → 보통은 어렵다. 일반 큐는 '현재 가장 싼 후보'를 먼저 꺼내 주지 못한다.
- 가중치가 있으면 항상 다익스트라다 → 아니다. 모두 같은 비용이면 BFS, 0/1이면 0-1 BFS가 가능하다.
- 다익스트라는 BFS의 상위 호환이다 → 이렇게 외우기보다, 거리 정의가 달라졌을 때 선택이 갈리는 알고리즘으로 이해하는 편이 정확하다.
정리
다익스트라가 등장하는 이유는 BFS가 틀려서가 아닙니다. 문제가 더 이상 간선 수를 거리로 보지 않기 때문입니다. BFS는 이동 횟수 기준, 다익스트라는 누적 비용 기준으로 최단 경로를 찾습니다.
그래서 가장 중요한 한 줄은 이것입니다. 이 문제의 거리 정의가 간선 수인지, 누적 비용인지부터 확인하자. 이 기준만 잡히면 BFS와 다익스트라의 경계가 훨씬 덜 헷갈립니다.
BFS 자체를 먼저 정리하고 싶다면 BFS(너비 우선 탐색) 알고리즘 글을 먼저 보고, 그래프 탐색 감각을 넓히고 싶다면 DFS와 BFS는 언제 다르게 써야 할까 글도 이어서 읽어보면 좋습니다.
외부 참고 자료는 cp-algorithms의 BFS 문서, Dijkstra 문서, 0-1 BFS 문서를 기준으로 정리했습니다.
