최단 경로 (Shortest Path) -- 코딩테스트 스터디 8주차
코딩테스트 스터디 8주차 학습 자료를 정리한 글이다.
1. 최단 경로 문제의 두 갈래
단일 출발점 vs 모든 쌍
최단 경로 문제는 출발점이 몇 개냐에 따라 두 유형으로 나뉜다.
단일 출발점 최단 경로(SSSP, Single Source Shortest Path) : 한 정점에서 나머지 모든 정점까지의 최단 거리를 구한다. 다익스트라가 대표적이다.모든 쌍 최단 경로(APSP, All Pairs Shortest Path) : 모든 정점 쌍 (i, j) 사이의 최단 거리를 한 번에 구한다. 플로이드-워셜이 대표적이다.
가중 그래프 표현
인접 리스트 방식으로 가중 그래프를 표현한다. graph[u]는 정점 u에서 출발하는 간선들을 (도착 정점, 가중치) 튜플의 리스트로 저장한다.
graph = {
1 : [(2 , 2 ), (3 , 5 ), (4 , 1 )],
2 : [(3 , 3 ), (4 , 2 )],
3 : [(5 , 1 )],
4 : [(3 , 3 ), (5 , 1 )],
5 : [],
}
플로이드-워셜은 2차원 거리 테이블 dist[i][j]를 사용한다. dist[i][j]는 정점 i에서 정점 j까지의 최단 거리다.
음수 간선과 음수 사이클
음수 간선 : 가중치가 0보다 작은 간선이다. 다익스트라는 음수 간선이 있으면 올바른 결과를 보장하지 못한다.음수 사이클 : 사이클을 이루는 간선들의 가중치 합이 음수인 경우다. 사이클을 반복할수록 거리가 줄어들어 최단 경로가 정의되지 않는다.
음수 간선이 있으면 벨만-포드(O(VE))를 사용한다.
알고리즘 선택표
알고리즘
출발점
음수 간선
시간복잡도
다익스트라
단일
불가
O((V+E)logV)
벨만-포드
단일
가능
O(VE)
플로이드-워셜
모든 쌍
가능
O(V³)
2. 다익스트라 알고리즘
BFS와의 차이
BFS는 간선 수가 적은 경로를 먼저 탐색한다. 모든 간선의 비용이 동일할 때는 BFS로 최단 경로를 구할 수 있다. 하지만 간선마다 가중치가 다르면 간선 수가 적더라도 비용이 더 클 수 있다. 다익스트라는 간선 수가 아닌 누적 비용 기준으로 탐색한다.
핵심 아이디어: 탐욕적 선택
현재까지 확정된 최단 거리 중 가장 작은 값을 가진 정점을 선택하고, 그 정점을 경유하는 경로로 인접 정점들의 거리를 갱신한다. 이 선택이 올바른 이유는 양수 가중치만 존재할 때, 한 번 선택된 정점의 최단 거리는 이후에 더 짧아질 수 없기 때문이다. 음수 가중치가 있으면 이 보장이 깨진다.
ASCII 단계별 진행도
정점 5개, 시작 정점 1번 기준 예시다.
간선 정보:
1→2 (2), 1→3 (5), 1→4 (1)
2→3 (3), 2→4 (2)
3→5 (1)
4→3 (3), 4→5 (1)
초기 상태:
dist = [INF, 0, INF, INF, INF, INF] (1번 인덱스가 시작점)
heap = [(0, 1)]
Step 1: pop (0, 1) → 정점 1 확정
1→2 갱신: dist[2] = 0+2 = 2
1→3 갱신: dist[3] = 0+5 = 5
1→4 갱신: dist[4] = 0+1 = 1
dist = [INF, 0, 2, 5, 1, INF]
heap = [(1, 4), (2, 2), (5, 3)]
Step 2: pop (1, 4) → 정점 4 확정
4→3 갱신: dist[3] = min(5, 1+3) = 4
4→5 갱신: dist[5] = min(INF, 1+1) = 2
dist = [INF, 0, 2, 4, 1, 2]
heap = [(2, 2), (2, 5), (5, 3), (4, 3)]
Step 3: pop (2, 2) → 정점 2 확정
2→3 갱신: dist[3] = min(4, 2+3) = 4 (변화 없음)
2→4 갱신: dist[4] = min(1, 2+2) = 1 (변화 없음)
dist = [INF, 0, 2, 4, 1, 2]
heap = [(2, 5), (4, 3), (5, 3)]
Step 4: pop (2, 5) → 정점 5 확정
5번 인접 간선 없음
dist = [INF, 0, 2, 4, 1, 2]
heap = [(4, 3), (5, 3)]
Step 5: pop (4, 3) → 정점 3 확정
3→5 갱신: dist[5] = min(2, 4+1) = 2 (변화 없음)
dist = [INF, 0, 2, 4, 1, 2]
heap = [(5, 3)]
Step 6: pop (5, 3) → cost(5) > dist[3](4), 스킵
heap = []
최종 dist = [INF, 0, 2, 4, 1, 2]
순진 구현의 한계
매 반복마다 미확정 정점 전체를 선형 탐색하면 O(V²)가 된다. V가 수만 이상이면 시간 초과가 발생하므로 우선순위 큐를 사용한다.
3. 우선순위 큐 기반 다익스트라
표준 구현
import heapq
def dijkstra (graph, start, n):
INF = float ('inf' )
dist = [INF] * (n + 1 )
dist[start] = 0
heap = [(0 , start)]
while heap:
cost, u = heapq.heappop (heap)
if cost > dist[u]:
continue
for v, w in graph[u]:
next_cost = cost + w
if next_cost < dist[v]:
dist[v] = next_cost
heapq.heappush (heap, (next_cost, v))
return dist
cost > dist[u] 조건은 중복 pop을 회피하기 위한 핵심 구문이다. 힙에는 같은 정점이 여러 번 삽입될 수 있다. 꺼낸 비용이 현재 확정된 최단 거리보다 크면 이미 더 짧은 경로로 처리된 항목이므로 건너뛴다.
시간 복잡도
힙에 삽입되는 횟수는 최대 간선 수 E다. 각 삽입/삭제는 O(log V)다. 전체 시간 복잡도는 O((V+E)log V)다.
실행 예시
graph = [[] for _ in range (6 )]
edges = [
(1 , 2 , 2 ), (1 , 3 , 5 ), (1 , 4 , 1 ),
(2 , 3 , 3 ), (2 , 4 , 2 ),
(3 , 5 , 1 ),
(4 , 3 , 3 ), (4 , 5 , 1 ),
]
for u, v, w in edges:
graph[u].append ((v, w))
result = dijkstra (graph, 1 , 5 )
print (result[1 :])
출력:
[0, 2, 4, 1, 2]
4. 플로이드-워셜 알고리즘
경유지 k 아이디어
정점 i에서 정점 j로 가는 최단 거리를 구할 때, 중간에 정점 k를 경유하는 경우와 경유하지 않는 경우를 비교한다. 모든 정점을 경유지 후보로 순서대로 시도하면 모든 쌍의 최단 거리를 구할 수 있다.
점화식
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
k를 가장 바깥 루프에 두어야 한다. 경유지 k를 고정한 상태에서 모든 (i, j) 쌍을 갱신해야, 이전 단계까지의 최적 경유 정보가 제대로 누적된다. k가 안쪽 루프이면 아직 확정되지 않은 경유 경로를 참조하게 되어 틀린 결과가 나온다.
초기화 주의사항
[[INF] * (n+1)] * (n+1) 형태는 같은 리스트 객체를 참조하므로 한 행을 수정하면 모든 행이 바뀐다. 반드시 리스트 컴프리헨션을 사용한다.
INF = float ('inf' )
dist = [[INF] * (n + 1 ) for _ in range (n + 1 )]
for i in range (1 , n + 1 ):
dist[i][i] = 0
자기 자신까지의 거리 dist[i][i]는 0으로 초기화한다.
2차원 표 진행도
정점 4개 예시다. 간선: 1→2(3), 1→4(7), 2→3(2), 3→4(1), 4→2(4)
초기 dist (간선 정보만 반영):
1 2 3 4
1 [ 0, 3, INF, 7]
2 [INF, 0, 2, INF]
3 [INF, INF, 0, 1]
4 [INF, 4, INF, 0]
k=1 경유: i→1→j 경로 반영
dist[2][4] = min(INF, INF+7) = INF (변화 없음)
→ 1번 정점으로 오는 간선이 없어 큰 변화 없음
k=2 경유: i→2→j 경로 반영
dist[1][3] = min(INF, 3+2) = 5
dist[4][3] = min(INF, 4+2) = 6
k=3 경유: i→3→j 경로 반영
dist[1][4] = min(7, 5+1) = 6
dist[2][4] = min(INF, 2+1) = 3
dist[4][4] = min(0, 6+1) = 0 (변화 없음)
k=4 경유: i→4→j 경로 반영
dist[1][2] = min(3, 6+4) = 3 (변화 없음)
dist[2][2] = min(0, 3+4) = 0 (변화 없음)
dist[3][2] = min(INF, 1+4) = 5
최종 dist:
1 2 3 4
1 [ 0, 3, 5, 6]
2 [INF, 0, 2, 3]
3 [INF, 5, 0, 1]
4 [INF, 4, 6, 0]
음수 사이클 탐지
플로이드-워셜 완료 후 dist[i][i] < 0인 정점이 있으면 음수 사이클이 존재한다. 자기 자신을 경유하는 경로의 비용이 음수라는 뜻이다.
구현 코드
def floyd_warshall (n, edges):
INF = float ('inf' )
dist = [[INF] * (n + 1 ) for _ in range (n + 1 )]
for i in range (1 , n + 1 ):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w
for k in range (1 , n + 1 ):
for i in range (1 , n + 1 ):
for j in range (1 , n + 1 ):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
실행 예시
n = 4
edges = [
(1 , 2 , 3 ), (1 , 4 , 7 ),
(2 , 3 , 2 ),
(3 , 4 , 1 ),
(4 , 2 , 4 ),
]
result = floyd_warshall (n, edges)
for i in range (1 , n + 1 ):
print (result[i][1 :])
출력:
[0, 3, 5, 6]
[inf, 0, 2, 3]
[inf, 5, 0, 1]
[inf, 4, 6, 0]
5. 두 알고리즘 비교
항목
다익스트라
플로이드-워셜
유형
단일 출발점
모든 쌍
음수 간선
불가
가능
시간복잡도
O((V+E)logV)
O(V³)
공간복잡도
O(V+E)
O(V²)
적합한 경우
V, E 크고 출발점 1개
V 작고(500 이하) 모든 쌍 필요
코딩테스트에서 V가 100~500 수준이고 모든 쌍 사이의 거리가 필요하면 플로이드-워셜을, V나 E가 크고 출발점이 하나라면 다익스트라를 선택한다.
6. Python 자주 쓰는 기법
heapq 기본 사용
import heapq
def heapq_example ():
heap = []
heapq.heappush (heap, (3 , 'c' ))
heapq.heappush (heap, (1 , 'a' ))
heapq.heappush (heap, (2 , 'b' ))
return [heapq.heappop (heap) for _ in range (3 )]
result = heapq_example ()
print (result)
출력:
[(1, 'a'), (2, 'b'), (3, 'c')]
Python의 heapq는 최소 힙이다. (비용, 정점) 튜플을 넣으면 비용 기준으로 정렬된다.
INF 사용
INF = float ('inf' )
print (INF + 100 )
print (INF > 10 ** 9 )
print (INF + INF)
출력:
inf
True
inf
float('inf')는 정수와 덧셈, 비교가 가능하다. INF + INF가 오류 없이 inf로 유지되어 점화식 갱신 시 안전하다.
defaultdict 인접 리스트
from collections import defaultdict
def build_graph (edges):
graph = defaultdict (list )
for u, v, w in edges:
graph[u].append ((v, w))
return graph
edges = [(1 , 2 , 3 ), (1 , 3 , 7 ), (2 , 3 , 2 )]
graph = build_graph (edges)
print (dict (graph))
출력:
{1: [(2, 3), (3, 7)], 2: [(3, 2)]}
2차원 리스트 초기화 주의
INF = float ('inf' )
n = 3
wrong = [[INF] * (n + 1 )] * (n + 1 )
wrong[1 ][1 ] = 0
print (wrong[2 ][1 ])
correct = [[INF] * (n + 1 ) for _ in range (n + 1 )]
correct[1 ][1 ] = 0
print (correct[2 ][1 ])
출력:
0
inf
* (n+1) 방식은 같은 리스트 객체를 참조하므로 한 행만 수정해도 모든 행이 바뀐다. 리스트 컴프리헨션으로 각 행을 독립적으로 생성해야 한다.
7. 연습 문제
문제
난이도
링크
핵심 접근
가장 먼 노드
Lv 3
프로그래머스 다익스트라(가중치 1인 그래프), 최댓값과 같은 거리의 노드 개수
배달
Lv 3
프로그래머스 다익스트라, K 이하 거리 마을 개수
합승 택시 요금
Lv 3
프로그래머스 플로이드-워셜, 합류 지점 k마다 dist[s][k]+dist[k][a]+dist[k][b] 최솟값
순위
Lv 3
프로그래머스 플로이드-워셜로 도달 가능 여부 계산, 승패 관계 n-1개 확정된 선수 카운트
