1. 점화식이 핵심
플로이드-워셜 알고리즘은 DP 기반 알고리즘이야.
이때 핵심 점화식은 다음과 같아:
D[i][j] = min(D[i][j], D[i][k] + D[k][j])여기서 D[i][j]는 i에서 j로 가는 현재 최단 거리이고,
k는 중간에 거쳐가는 정점이야.
즉, **"i에서 j로 가는 현재 경로보다, i→k→j로 가는 경로가 더 짧으면 갱신하겠다"**는 뜻이야.
2. 갑자기 궁금증
1. a -> b -> c
a에서 c까지 간다고 할 때 그냥 다 더하면 되는 건가?
a → b까지의 cost가 있고 (예:D[a][b])b → c까지의 cost가 있고 (예:D[b][c])- 그러면
a → b → c는D[a][b] + D[b][c]
2. 그런데 중간 경유지 K는 뭐야?
예를 들어, k = b라고 한다면 우리는 **"모든 i → j 경로에 대해서, b를 경유해서 갈 경우 더 짧은가?"**를 확인해야 한다. 즉, "i → b + b → j" 와 기존의 "i → j" 중 누가 더 짧은가?"
이걸 수식으로 표현하면:
D[i][j] = min(D[i][j], D[i][k] + D[k][j])3. 그러면 결론은 어떻게 해야 되는 건데?
경로가 기존보다 짧은지를 비교하고, 짧으면 업데이트하는 것
a → c의 기존 최단 거리:D[a][c]- 새롭게 생각해볼 수 있는 경유 경로:
a → b + b → c = D[a][b] + D[b][c]
→ 이제 D[a][c]를 갱신하는 거야:
D[a][c] = min(D[a][c], D[a][b] + D[b][c])이걸 모든 (i, j) 쌍에 대해, 그리고 k를 1부터 N까지 반복하면서 수행해야 한다.
3. 왜 k가 바깥 for문일까?
for k in range(1, N+1):
for i in range(1, N+1):
for j in range(1, N+1):
D[i][j] = min(D[i][j], D[i][k] + D[k][j])→ 왜 k가 가장 바깥에 오냐면, "지금은 k번 정점까지를 경유할 수 있다고 가정하고" 그 상태에서 모든 i, j 쌍을 업데이트해야 하기 때문.
즉, k를 점점 늘려가면서 경유 가능한 정점의 수를 늘리는 패턴.
하나의 k에 대해 모든 경로 (i, j)를 업데이트!!
4. 플로이드-워셜의 의미 다시 짚기
플로이드-워셜은 **동적 계획법(DP)**을 기반으로 하는 알고리즘이다.
우리가 D[i][j]를 갱신할 때 D[i][k] + D[k][j]를 사용하기 때문에 "이미 계산된 i→k, k→j 경로 정보를 바탕으로"
i→j를 갱신하는 것.
→ 즉, 신뢰할 수 있는(k까지의) 정보만을 바탕으로 갱신해야 함.
for문 순서가 바뀌면 어떤 일이 생기나?
가령 아래처럼 순서를 바꾼다고 가정해보면:
for i in range(1, N+1):
for j in range(1, N+1):
for k in range(1, N+1):
D[i][j] = min(D[i][j], D[i][k] + D[k][j])이건 지금 뭘 의미하냐면,
i → j경로를 먼저 정하고- 그 다음, 모든 k를 시도해서 경유해보는 것이다.
문제는 뭐냐면, 이때 사용되는 D[i][k]와 D[k][j]가 최신 상태가 아닐 수 있다는 거임.
예를 들어,
k=2일 때D[i][2]가 실제로 더 짧아졌는데- 그걸 고려하지 않은 채
k=3일 때D[i][3]를 계산하고 있으면, - 더 짧은 경로를 놓치는 것이다.
k를 바깥에 둔다는 것의 의미
for k in range(1, N+1): # 중간에 경유할 수 있는 정점 수를 1개씩 늘려감
for i in range(1, N+1): # 시작점
for j in range(1, N+1): # 도착점
D[i][j] = min(D[i][j], D[i][k] + D[k][j])이 구조의 의미는:
- **"k까지의 정점만 경유 가능"하다는 제한을 두고 최단 경로를 구하자"**는 뜻.
- 그러니까,
k = 1이면 "1번 정점만 경유 가능"k = 2이면 "1번, 2번 정점 경유 가능"- …
k = N이면 "모든 정점 경유 가능"
이렇게 되면, 경유지로 사용할 수 있는 정점 수가 점점 늘어나는 상황에서 그때그때 가능한 정보만으로 최단 경로를 갱신할 수 있다.
요약
| for문 순서 | 의미 | 왜 문제되나 |
|---|---|---|
for k → i → j | 경유 가능한 정점을 하나씩 늘리며, 해당 k까지의 정보만으로 갱신 | 안전하게 최단 거리만을 사용 |
for i → j → k | 아직 경유 가능한 정점이 뭔지도 모르는 상태에서 k를 사용 | 최신 정보가 아님 → 틀린 경로로 갱신될 수 있음 |
실험
예시
정점 수: 3개 (1, 2, 3)
간선 정보 (단방향, 가중치 있음):
- 1 → 2 : 4
- 2 → 3 : 2
- 1 → 3 : 10
생각 정리
- 1 → 3 직접 가면 cost = 10
- 1 → 2 → 3 경유하면 cost = 4 + 2 = 6
→ 그러니까, 1 → 3은 1→2→3으로 갱신되어야 함
실험 목표
두 가지 방식으로 D[1][3]이 어떻게 갱신되는지 비교해보면:
A. 올바른 순서 (for k → i → j)
for k in range(1, 4):
for i in range(1, 4):
for j in range(1, 4):
D[i][j] = min(D[i][j], D[i][k] + D[k][j])→ 이 경우 D[1][3]은 10 → 6으로 갱신됨.
B. 잘못된 순서 (for i → j → k)
for i in range(1, 4):
for j in range(1, 4):
for k in range(1, 4):
D[i][j] = min(D[i][j], D[i][k] + D[k][j])→ 이 경우 D[1][3]은 여전히 10일 수 있지 않나?
→ 이유: D[1][2]나 D[2][3]이 아직 제대로 반영되지 않은 상태에서 D[1][3]을 계산했으니까 그럴 수 있다고 생각함.
구현
N = 3
INF = 1e9
D = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
D[i][i] = 0
# 간선 정보 입력
D[1][2] = 4
D[2][3] = 2
D[1][3] = 10
for k in range(1, N + 1):
for i in range(1, N + 1):
for j in range(1, N + 1):
D[i][j] = min(D[i][j], D[i][k] + D[k][j])
print(f'출발 지점 : {i}, 경유 지점 : {k}, 도착 지점 : {j}')
print(D[1][3])
D = [[INF] * (N + 1) for _ in range(N + 1)]
# 간선 정보 입력
D[1][2] = 4
D[2][3] = 2
D[1][3] = 10
for i in range(1, N + 1):
for j in range(1, N + 1):
for k in range(1, N + 1):
D[i][j] = min(D[i][j], D[i][k] + D[k][j])
print(D[1][3])실험 결과
6
6왜 10이 아니지??
[i=1, j=1, k=1] 기존: 1000000000.0, 경유경로: 1000000000.0 + 1000000000.0 = 2000000000.0 → 갱신결과: 1000000000.0
[i=1, j=1, k=2] 기존: 1000000000.0, 경유경로: 4 + 1000000000.0 = 1000000004.0 → 갱신결과: 1000000000.0
[i=1, j=1, k=3] 기존: 1000000000.0, 경유경로: 10 + 1000000000.0 = 1000000010.0 → 갱신결과: 1000000000.0
[i=1, j=2, k=1] 기존: 4, 경유경로: 1000000000.0 + 4 = 1000000004.0 → 갱신결과: 4
[i=1, j=2, k=2] 기존: 4, 경유경로: 4 + 1000000000.0 = 1000000004.0 → 갱신결과: 4
[i=1, j=2, k=3] 기존: 4, 경유경로: 10 + 1000000000.0 = 1000000010.0 → 갱신결과: 4
[i=1, j=3, k=1] 기존: 10, 경유경로: 1000000000.0 + 10 = 1000000010.0 → 갱신결과: 10
[i=1, j=3, k=2] 기존: 10, 경유경로: 4 + 2 = 6 → 갱신결과: 6
[i=1, j=3, k=3] 기존: 6, 경유경로: 6 + 1000000000.0 = 1000000006.0 → 갱신결과: 6
[i=2, j=1, k=1] 기존: 1000000000.0, 경유경로: 1000000000.0 + 1000000000.0 = 2000000000.0 → 갱신결과: 1000000000.0
[i=2, j=1, k=2] 기존: 1000000000.0, 경유경로: 1000000000.0 + 1000000000.0 = 2000000000.0 → 갱신결과: 1000000000.0
[i=2, j=1, k=3] 기존: 1000000000.0, 경유경로: 2 + 1000000000.0 = 1000000002.0 → 갱신결과: 1000000000.0
[i=2, j=2, k=1] 기존: 1000000000.0, 경유경로: 1000000000.0 + 4 = 1000000004.0 → 갱신결과: 1000000000.0
[i=2, j=2, k=2] 기존: 1000000000.0, 경유경로: 1000000000.0 + 1000000000.0 = 2000000000.0 → 갱신결과: 1000000000.0
[i=2, j=2, k=3] 기존: 1000000000.0, 경유경로: 2 + 1000000000.0 = 1000000002.0 → 갱신결과: 1000000000.0
[i=2, j=3, k=1] 기존: 2, 경유경로: 1000000000.0 + 6 = 1000000006.0 → 갱신결과: 2
[i=2, j=3, k=2] 기존: 2, 경유경로: 1000000000.0 + 2 = 1000000002.0 → 갱신결과: 2
[i=2, j=3, k=3] 기존: 2, 경유경로: 2 + 1000000000.0 = 1000000002.0 → 갱신결과: 2
[i=3, j=1, k=1] 기존: 1000000000.0, 경유경로: 1000000000.0 + 1000000000.0 = 2000000000.0 → 갱신결과: 1000000000.0
[i=3, j=1, k=2] 기존: 1000000000.0, 경유경로: 1000000000.0 + 1000000000.0 = 2000000000.0 → 갱신결과: 1000000000.0
[i=3, j=1, k=3] 기존: 1000000000.0, 경유경로: 1000000000.0 + 1000000000.0 = 2000000000.0 → 갱신결과: 1000000000.0
[i=3, j=2, k=1] 기존: 1000000000.0, 경유경로: 1000000000.0 + 4 = 1000000004.0 → 갱신결과: 1000000000.0
[i=3, j=2, k=2] 기존: 1000000000.0, 경유경로: 1000000000.0 + 1000000000.0 = 2000000000.0 → 갱신결과: 1000000000.0
[i=3, j=2, k=3] 기존: 1000000000.0, 경유경로: 1000000000.0 + 1000000000.0 = 2000000000.0 → 갱신결과: 1000000000.0
[i=3, j=3, k=1] 기존: 1000000000.0, 경유경로: 1000000000.0 + 6 = 1000000006.0 → 갱신결과: 1000000000.0
[i=3, j=3, k=2] 기존: 1000000000.0, 경유경로: 1000000000.0 + 2 = 1000000002.0 → 갱신결과: 1000000000.0
[i=3, j=3, k=3] 기존: 1000000000.0, 경유경로: 1000000000.0 + 1000000000.0 = 2000000000.0 → 갱신결과: 1000000000.0모든 경우를 탐색하지 않아도 최단 경로가 탐색 되었기 때문
[i=1, j=3, k=2] 기존: 10, 경유경로: 4 + 2 = 6 → 갱신결과: 6왜 1 → 3 → 3 같은 쓸모없는 경로까지 계산하지?
플로이드-워셜 알고리즘의 구조적 특성과 관련 있다
핵심 개념부터 다시 보자
D[i][j] = min(D[i][j], D[i][k] + D[k][j])이건 모든 i, j 쌍에 대해, 중간에 어떤 k 정점을 거쳐서 가는 게 더 나은지 확인하는 로직이다.
그럼 당연히 i == k, k == j, i == j일 수도 있고, i → k → j가 도달 불가능하거나 의미 없는 경로일 수도 있음.
그런데도 왜 다 확인을 해야 할까?
이유 1: 모든 케이스를 단일한 로직으로 처리하기 위해
1 → 3 → 3의 의미를 보면:
i = 1,j = 3,k = 3- 즉, "3을 경유해서 1 → 3으로 가는 경로가 더 낫나?"
근데 사실 여기서 D[3][3]은 0 (자기 자신이니까), D[1][3] + D[3][3] = D[1][3] + 0 = D[1][3]
→ 결국 갱신되지 않음
즉, 계산은 하되 실제로 갱신은 안 되는 것임.
→ 이게 의미 없는 계산처럼 보일 수 있지만, 틀린 건 아님
이유 2: 알고리즘을 단순화하려는 의도
플로이드-워셜은 모든 i, j, k 조합을 단순히 3중 for문으로 처리하면 끝임.
- 복잡한 조건 분기를 만들지 않아도 됨 (예:
if i != k and k != j같은 것들) - 예외 없이 모든 경로를 동일한 방식으로 처리할 수 있음.
- 구현이 훨씬 깔끔하고 실수가 줄어듦.
→ 느려 보일 수는 있지만, 안전하고 일관된 방식임.
이유 3: 나중에 '자기 자신으로 돌아오는 최소 비용'도 계산하려면 필요함
이 부분은 나도 몰랐던 개념이긴 한데:
D[i][i]는 i에서 출발해서 다시 돌아오는 최소 비용, 즉 사이클 비용- 이걸 구하려면 경유지가 자기 자신인 경우도 고려해야 한다고 함
예: D[2][2] = min(D[2][2], D[2][3] + D[3][2]) 이런 식으로
→ 특히 음수 사이클 탐지에 사용됨
요약 정리
| 왜 계산하나? | 이유 |
|---|---|
i → k → j가 의미 없어 보일 때도 계산하는 이유 | 모든 경우를 빠짐없이 일괄 처리하려는 구조 때문 |
| 의미 없는 값이 갱신되진 않음 | 실제 min()에서 필터링됨 |
| 더 효율적으로 하려면 조건 넣을 수는 있음 | 하지만 코드 복잡도와 실수 가능성 증가 |
플로이드 워셜 알고리즘을 사용해서 최소비용 구하기 구현
import sys
INF = float('inf')
class answer:
def __init__(self, *args, **kwargs):
self.n = int(sys.stdin.readline())
self.m = int(sys.stdin.readline())
def build_graph(self):
self.graph = [[INF]*(self.n + 1) for _ in range(self.n + 1)]
for i in range(1, self.n + 1):
self.graph[i][i] = 0
def add_edge(self):
for _ in range(self.m):
a, b, c = map(int, sys.stdin.readline().split())
self.graph[a][b] = c
def floyd_warshall(self):
start, end = map(int, sys.stdin.readline().split())
for k in range(1, self.n + 1):
for i in range(1, self.n + 1):
for j in range(1, self.n + 1):
self.graph[i][j] = min(self.graph[i][j], self.graph[i][k] + self.graph[k][j])
return self.graph[start][end]
ans = answer()
ans.build_graph()
ans.add_edge()
print(ans.floyd_warshall())