최소 환승 문제란?
지하철 노선도를 떠올려 보세요. 어떤 역에서 다른 역으로 갈 때, "통로(연결)를 최소 몇 번 타야 하는가?"를 묻는 문제가 바로 최소 환승(최소 이동) 문제입니다.
핵심은 모든 연결의 길이가 같다(가중치 없음)는 점입니다. 그러면 "최소 이동 횟수 = 최소 간선 수"가 되고, 이것은 BFS(너비 우선 탐색)로 정확히 풀립니다.
왜 BFS인가?
BFS는 시작 역에서 가까운 역(레벨)부터 차례로 방문합니다.
- •레벨 0: 출발역 자신 (이동 0회)
- •레벨 1: 출발역과 통로 1개로 연결된 역들 (이동 1회)
- •레벨 2: 거기서 한 번 더 간 역들 (이동 2회)
같은 레벨을 모두 본 뒤 다음 레벨로 넘어가기 때문에, 목적역을 큐에서 처음 꺼내는 순간의 거리가 곧 최소 이동 횟수입니다. DFS로는 이 최단성을 보장할 수 없습니다.
동작 원리
1단계. 인접 리스트로 그래프를 만듭니다. 통로는 양방향이므로 두 역에 서로를 추가합니다.
2단계. 거리 배열 dist를 모두 -1(미방문)로 두고, 출발역만 dist[s] = 0으로 설정한 뒤 큐에 넣습니다.
3단계. 큐가 빌 때까지 역을 하나 꺼냅니다. 꺼낸 역이 목적역이면 그 거리를 즉시 반환합니다.
4단계. 꺼낸 역의 이웃 중 dist == -1인(아직 방문 안 한) 이웃에 대해 dist[next] = dist[cur] + 1을 기록하고 큐에 넣습니다.
여기서 방문 표시(거리 기록)를 큐에 넣는 순간에 해야 같은 역이 큐에 두 번 들어가지 않습니다.
그래프 탐색의 세 가지 분기
각 이웃을 볼 때 다음을 구분합니다.
- •이미 방문한 역 —
dist != -1→ 건너뜀 (중복·무한 루프 방지) - •연결 안 된 역 — 애초에 이웃 목록에 없으므로 자연히 제외
- •미방문 역 —
dist == -1→ 거리 +1 기록 후 큐에 추가
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(V + E) |
| 공간 | O(V) |
모든 역(V)과 통로(E)를 최대 한 번씩만 보기 때문에 O(V + E)입니다.
자주 하는 실수
- •방문 표시를 꺼낼 때 하면 같은 역이 큐에 여러 번 들어가 비효율·오답이 됩니다. 넣을 때 표시하세요.
- •가중치가 다른 그래프(통로마다 시간이 다름)에는 BFS가 아니라 다익스트라가 필요합니다.
- •도달 불가능한 경우(-1) 반환을 빠뜨리지 마세요.
알고노트에서 직접 확인하세요
큐가 레벨 순서로 채워지고, 거리 배열이 한 칸씩 늘어나며, 목적역을 꺼내는 순간 답이 확정되는 과정을 알고노트에서 한 스텝씩 볼 수 있습니다.