Python - < 13 >

개요

이번에 배운 건 최단 경로를 구하는 알고리즘 세 가지다. 다익스트라, 벨만-포드, 플로이드-워셜. 셋 다 “가장 싼 길”을 찾지만 쓰는 자리가 다르고, 그 자리를 가르는 건 두 질문이다.

• 몇 쌍을 묻는가. 한 점에서 출발하는 거리면 다익스트라·벨만-포드, 모든 점 사이의 거리면 플로이드-워셜
• 음수 간선을 믿을 수 있는가. 간선이 전부 0 이상이면 다익스트라, 음수가 섞이면 벨만-포드·플로이드-워셜

세 알고리즘이 맞는 이유를 한 문장씩으로 줄여 두면, 그 문장이 깨지는 조건도 같이 보인다.

• 다익스트라: 큐에서 꺼낸 순간 거리가 확정된다. 간선이 0 이상일 때만 참이다
• 벨만-포드: V−1바퀴 돌면 충분하다. 음수 사이클이 없을 때만 참이다
• 플로이드-워셜: 경유지 k가 가장 바깥 루프여야 한다. 안쪽으로 옮기면 재료가 준비되기 전에 칸이 확정된다

세 알고리즘 비교

	묻는 것	음수 간선	방식	시간
다익스트라	한 점 → 모든 점	✗	탐욕	O((V+E) log V) 힙 / O(V²) 배열
벨만-포드	한 점 → 모든 점	○, 음수 사이클 감지	DP	O(VE)
플로이드-워셜	모든 점 → 모든 점	○, 음수 사이클이면 불가	DP	O(V³), 공간 O(V²)

“모든 쌍이면 다익스트라를 V번 돌려도 되지 않나?”도 따져 볼 만하다. 힙 다익스트라를 V번 돌리면 O(V·(V+E) log V)다. 간선이 빽빽한 그래프( E ≈ V² )에서는 V³ log V라 플로이드가 낫고, 간선이 듬성한 그래프( E ≈ V )에서는 V² log V라 다익스트라 V번이 낫다. 둘의 복잡도가 같다고 뭉뚱그리면 이 차이가 사라진다.

다익스트라 — 꺼낸 순간 확정된다

다익스트라가 맞는 이유는 한 문장이다. 큐에서 정점 v를 거리 d로 꺼낸 순간, d가 v의 최종 최단 거리다. 이게 참이라서 꺼낸 정점을 다시 보지 않아도 된다.

왜 참인지 따라가 보자. d는 아직 확정되지 않은 정점 중 최솟값이다. v로 가는 다른 길이 있다면 그 길은 확정된 영역을 벗어나야 하고, 벗어나는 지점까지 이미 d 이상이 든다. 거기에 남은 간선을 더해도 간선 값이 0 이상이라 d 밑으로 내려가지 않는다.

이 증명에서 “간선 ≥ 0”이 쓰이는 곳은 마지막 문장 하나다. 음수 간선이 깨뜨리는 지점도 정확히 거기다.

BFS가 최단을 보장하는 것과 같은 구조다. BFS는 큐에서 꺼내는 거리가 줄어들지 않아서 처음 꺼낸 순간이 최단이다. 간선 비용이 제각각이면 그냥 큐로는 이 순서가 안 지켜지니, 다익스트라는 우선순위 큐로 “가장 가까운 것부터”를 유지한다.

import heapq

def dijkstra(adj, start, n):
    INF = float('inf')
    dist = [INF] * n               # 지금까지 알아낸 최소 비용
    dist[start] = 0
    pq = [(0, start)]              # (거리, 정점) — 거리가 작은 것부터 나온다
    while pq:
        d, v = heapq.heappop(pq)   # 미확정 중 가장 가까운 정점
        if d > dist[v]:            # 더 짧은 값으로 이미 처리된 낡은 항목
            continue
        for w, nxt in adj[v]:
            if d + w < dist[nxt]:  # 더 짧을 때만 갱신
                dist[nxt] = d + w
                heapq.heappush(pq, (dist[nxt], nxt))
    return dist

갱신될 때마다 새 항목을 넣고 낡은 항목은 꺼낼 때 버리는( lazy deletion ) 방식이라 힙 크기는 최대 E다. log E ≤ log V² = 2 log V라서 O((V+E) log V)로 쓴다.

visited 없이 “더 짧으면 다시 넣는” 이 구현은 음수 간선이 있어도( 음수 사이클만 없으면 ) 답은 맞는다. 같은 정점을 여러 번 다시 처리할 뿐이다. 다만 최악에는 처리 횟수가 지수적으로 커질 수 있다고 알려져 있다. 반대로 visited로 한 번 꺼낸 정점을 막아 버리면 위 그림처럼 틀린 답을 낸다.

벨만-포드 — 왜 V−1바퀴면 되나

벨만-포드는 “누가 확정됐는가”를 판단하지 않는다. 모든 간선을 반복해서 완화한다.

간선 u→v로 갱신한 값이 정답이 되려면, 그 순간 dist[u]가 이미 정답이어야 한다. 그래서 간선을 검사하는 순서가 속도를 좌우한다.

순서가 아무리 나빠도 한 바퀴에는 모든 간선이 한 번씩 검사된다. 그러니 “정답이 맞은 영역의 바로 다음 칸”은 바퀴마다 최소 한 칸 전진한다. i바퀴 뒤에는 간선 i개 이하로 된 최단 경로가 전부 정답이다.

음수 사이클이 없으면 최단 경로는 같은 정점을 두 번 지날 이유가 없다. 사이클을 한 바퀴 돌면 0 이상이 더해질 뿐이다. 그래서 최단 경로의 간선은 최대 V−1개다.

두 문장을 합치면 상한이 나온다. 한 바퀴에 최소 한 칸 × 최대 V−1칸 = V−1바퀴.

수업 예제가 2바퀴 만에 멈춘 건 간선 순서가 좋은 순서에 가까웠기 때문이고, 갱신이 없으면 끝내는 조기 종료가 그런 경우를 위한 최적화다.

def bellman_ford(edges, start, n):
    INF = float('inf')
    dist = [INF] * n
    dist[start] = 0
    for _ in range(n - 1):                         # 최대 V-1바퀴
        updated = False
        for u, v, w in edges:                      # 매 바퀴 모든 간선 검사
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:                            # 한 바퀴 내내 갱신이 없으면 끝
            break
    for u, v, w in edges:                          # 한 바퀴 더: 갱신되면 음수 사이클
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None
    return dist

음수 사이클

한 바퀴 합이 음수인 사이클이 있으면 돌수록 거리가 줄어서 “최단 거리”가 정의되지 않는다( −∞ ). 감지는 위 코드 마지막 부분처럼 V−1바퀴 뒤에 한 바퀴를 더 돈다. 그때도 갱신이 일어나면 “최단 경로 간선은 V−1개 이하”라는 전제가 깨졌다는 뜻이고, 그러려면 음수 사이클이 있어야 한다. 추가 비용은 O(E)다.

dist[u] != INF 조건 때문에 시작점에서 닿지 않는 음수 사이클은 감지되지 않는다. 시작점에서 갈 수 없으니 결과에도 영향이 없어서 합리적인 동작이다.

−∞가 되는 정점을 “사이클에 도달할 수 있는 정점”으로 착각하기 쉬운데, 정확히는 사이클에서 출발해 도달할 수 있는 정점이다.

F는 사이클로 들어가는 간선만 있어서 F까지의 거리는 사이클을 몇 바퀴 돌든 상관없이 2다. D는 사이클을 돌고 나서 닿을 수 있으니 같이 −∞가 된다.

플로이드-워셜 — k가 가장 바깥에 있어야 하는 이유

플로이드를 “환승 허가제”로 보면 루프 순서가 이해된다. k라운드는 “1~k번 정점에서 환승을 허용”하는 단계다. 라운드마다 모든 쌍 (i, j)에 대해 “새로 허가된 k를 거치면 더 짧아지나?”를 확인한다.

for k in range(n):              # k번 정점에서 환승을 새로 허가
    for i in range(n):          # 출발
        for j in range(n):      # 도착
            if D[i][k] + D[k][j] < D[i][j]:
                D[i][j] = D[i][k] + D[k][j]

k라운드 계산에는 k−1라운드 결과가 표 전체에 대해 완성돼 있어야 한다. 그래서 k가 가장 바깥이다. k를 안쪽으로 옮기면( for i: for j: for k: ) 칸 하나를 끝까지 계산하고 다시 보지 않는데, 그 시점에 재료가 될 다른 칸이 아직 비어 있을 수 있다.

이건 작은 그래프에서만의 일이 아니다. 수업 자료의 5정점 예제 그래프에 k 안쪽 순서를 돌리면 D[1][2], D[2][1], D[5][1] 세 칸이 틀린다( 정답 1, 0, −3 대신 4, 2, −1 ).

표 하나를 덮어써도 되는 이유

k라운드에서 읽는 값은 k번 행과 k번 열뿐이다. 그런데 그 값들 자신은 이번 라운드에서 바뀌지 않는다.

D[i][k] = min( D[i][k], D[i][k] + D[k][k] )    D[k][k] = 0이라 그대로

그래서 라운드마다 표를 새로 만들지 않고 제자리에서 덮어써도 되고, 공간이 O(V²) 하나로 끝난다.

음수 사이클이 있으면 D[k][k]가 음수가 될 수 있어서 이 논리가 깨진다. 거꾸로 끝난 뒤 D[i][i] < 0인 칸이 있으면 음수 사이클이 있다는 감지법이 여기서 나온다.

게임에서 고르기 — A*와 미리 계산

A*는 우선순위만 바꾼 다익스트라다

A*는 큐의 우선순위를 f = g + h로 바꾼다. g는 지금까지 온 실제 거리, h는 목적지까지 남은 거리의 추정치다. h = 0이면 다익스트라와 같다.

최단을 보장하려면 h가 실제 남은 거리보다 크면 안 된다( 과대평가 금지, admissible ). 상하좌우로만 움직이는 격자에서 흔히 쓰는 h는 맨해튼 거리

dx

+

dy

다. 바둑판 도로를 꺾어 가는 거리라서, 칸 비용이 최소 1이면 실제 남은 비용은 언제나 맨해튼 거리 이상이다. 직선 거리 √(dx² + dy²)는 상하좌우 이동으로는 낼 수 없는 거리다.

h를 일부러 부풀리면 최단 보장이 사라지는 대신 목적지 쪽으로 쏠려서 탐색이 빨라진다. 풀밭 1, 늪 3인 작은 맵에서 비교해 보면 이렇다.

h × 3이면 아래 줄 우회로의 f가 부풀어서 한 번도 꺼내지지 않고, 늪을 직진한 비용 8을 돌려준다. h에 가중치 w를 곱하는 이 방식( Weighted A* )은 결과가 최단의 w배를 넘지 않는다는 보장만 남긴다( 8 ≤ 3 × 6 ).

플로이드는 작은 그래프에 미리 돌려 둔다

플로이드는 타일 단위의 큰 맵에는 못 쓴다. 타일 1만 개면 표가 1억 칸이다. 대신 방·구역 100개 같은 추상 그래프라면 로딩 때 한 번 돌려 두고 런타임에는 O(1)로 조회할 수 있다. next[i][j]( i에서 j로 갈 때 다음에 밟을 정점 )를 같이 기록하면 경로도 복원된다.

벨만-포드는 경제 데이터 검사에

재화를 정점, 교환·제작 비율을 간선으로 두고 가중치를 −log(비율)로 바꾸면 비율의 곱이 가중치의 합이 된다. 그러면 음수 사이클이 “돌릴수록 재화가 불어나는 교환 루프”, 무한 재화 버그다. 실무 사례를 확인한 건 아니고, 알고리즘 성질에서 나온 아이디어다.

상황	선택	이유
유닛 하나 → 목적지 하나	A*	목적지 방향으로만 탐색
한 지점에서 맵 전체 거리	다익스트라	목적지가 “전부”라 방향 감각이 소용없음
경제 데이터의 무한 재화 루프 검사	벨만-포드	음수 가중치 + 음수 사이클 감지
작은 구역 그래프의 모든 쌍	플로이드	미리 계산 후 O(1) 조회

SWEA 22380 호준이의 기차 여행 — 400초에서 일부 오답까지

문제. 정점 N개( 1 ≤ N ≤ 2,000 ), 방향 간선 최대 300,000개가 (a, b, w)로 주어진다( a ≠ b, 1 ≤ w ≤ 10,000 ). 0번에서 N−1번까지 가는 최소 비용을 출력하고, 길이 없으면 impossible을 출력한다.

플로이드에서 다익스트라로

처음엔 N 범위를 보지도 않고 플로이드-워셜로 짜서 냈고, 시간 초과가 났다.

플로이드-워셜은 모든 역에서 모든 역까지의 최소 요금을 한 표에 채운다. 역이 2,000개면 표는 2,000 × 2,000 = 400만 칸이고, 칸마다 “중간에 들를 역” 2,000개를 하나씩 따져 본다. 2000³ = 80억 번, 초당 2000만 번으로 잡으면 약 400초다. 시간 초과가 날 수밖에 없었다..

따져 보니 출력은 0번에서 마지막 역까지의 요금 한 칸인데, 나머지 399만 9999칸까지 전부 채우고 있었다.

묻는 건 “한 점 → 한 점”이니 위 표의 다익스트라 칸이고, 가중치가 1 이상이라 다익스트라의 전제( 간선 ≥ 0 )도 만족한다. 목적지가 하나면 목적지를 꺼낸 순간 멈춰도 된다. 꺼낸 순간 확정되니까.

이번에는 힙 없이 배열 버전으로 짰다. costs( 지금까지 알아낸 최소 비용 )와 visited( 확정 여부 ) 두 배열만 쓰고, 매 바퀴 미확정 정점 N개를 직접 훑어 최솟값을 고른다. 총 N × N이다.

한 바퀴는 네 단계다.

1. 미확정 정점 중 비용이 가장 작은 정점을 고른다
2. 그 최솟값이 INF면 더 갈 수 있는 곳이 없으니 멈춘다
3. 확정한다. 목적지면 멈춘다
4. 이웃의 비용을 갱신한다

정점마다 한 번만 확정되니 힙 버전의 “꺼낸 값이 기록값보다 크면 건너뛰기” 확인이 필요 없다.

# 배열 버전 다익스트라(수정 전)
costs = [INF] * N
costs[0] = 0
visited = [False] * N
adj_list = [[] for _ in range(N)]
for _ in range(M):
    start, end, cost = map(int, input().split())
    adj_list[start].append((cost, end))

for pos in range(N):
    min_cost, min_pos = INF, -1
    for v in range(N):
        if visited[v]: continue
        if min_cost > costs[v]:
            min_cost = costs[v]
            min_pos = v
    if min_cost == INF: break
    visited[min_pos] = True
    if min_pos == N - 1: break
    for cost, end in adj_list[min_pos]:
        costs[end] = min_cost + cost   # 버그: 비교 없이 덮어씀

일부 케이스만 틀렸다

시간 초과는 사라졌는데 일부 테스트 케이스가 틀렸다. 원인은 탐욕 선택이 아니라 마지막 줄이었다. “더 작을 때만” 갱신하지 않고 무조건 덮어쓴다.

0번을 확정하면 costs[2]는 3이 된다. 다음으로 1번( 비용 1 )을 확정하면 간선 1→2( 10 )가 costs[2]를 1 + 10 = 11로 덮어쓰고, 답이 11이 된다. 비싼 간선이 나중에 처리되는 모양일 때만 터지니 일부 케이스만 틀렸다.

    for cost, end in adj_list[min_pos]:
        costs[end] = min(costs[end], min_cost + cost)   # 기존 값보다 작을 때만 갱신

이렇게 고쳐서 통과했다. 다익스트라든 벨만-포드든 플로이드든 갱신은 전부 “더 작을 때만”이다. 무조건 대입은 일부 그래프에서만 틀려서 찾기가 어렵다.

같이 나온 구현 주의점

• 파이썬 list.pop()은 맨 뒤 원소를 꺼낸다( 스택 ). 다익스트라의 “가장 가까운 것 꺼내기”를 보장하지 않으니 heapq나 직접 최솟값 찾기를 쓴다
• 인접 행렬에 costs[start][end] = cost로 넣으면 같은 구간 간선이 여러 번 주어질 때 나중 값으로 덮인다. 인접 리스트는 둘 다 저장되니 자연히 해결된다
• [x] * N은 숫자라 안전하지만 [[x] * N] * N은 모든 행이 같은 리스트를 공유한다

소감