[Python] 백준 - 11404 플로이드

 

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

 

문제해결방법 - 

 

1. 플로이드 와샬 알고리즘이라고 하는 방법을 활용해야 하는데, 전 포스팅인 벨만포드알고리즘 문제처럼 금방 떠올려서 해결할 수 있는 문제는 아닌 것 같고, 그렇다고 백지부터 조금씩 퍼즐을 맞추고, 참고하여 풀기에는 부적절하다.

 

2. 코드를 보며, 3중 for문과 원리를 이해하도록 하자. 코드는 엄청 간단한데 헷갈린다. ;

피상적으로는 이해되는데, 정확한 작동 원리는 아직도 헷갈린다..;

 

3. for문의 의미.

 

1) 첫번째 for문의 반복되는 인덱스는 중간 경유지이다.

2) 두번째, 세번째의 인덱스는 시작점과 도착점이다.

 

4. 경유지를 고정해놓고, 모든 dp를 돌고, 그다음 경유지 고정해놓고 모든 dp를 돌아 최소값으로 반영한다.

 

헷갈리는 점-

 

ex)

[1]과 [5] 사이의 최소값이라면 [1][2] +[2][5] ~ [1][4] + [4][5] 중 최소값이 존재할텐데,

[1][2]의 최소값은 또 [1][5]+ [5][2]이 될 수도 있다는 것 때문에 반영이 안되는 경우가 있지 않을까 생각이 들었고, 명확하게 정리가 되지 않았다. 또 [1][5]는 [1][?] + [?][5] 로 계속 반복될 수도 있지 않을까 하는 수렁ㅠㅠ

 

일단 잠정적으로 내린 결론(너무 복잡하게 생각하는 것일 수도 있다. 귀납적으로 하나하나 검토해보면 뭔가 알 수도 있을 것 같긴 한데, 일단 아래와 같게 생각하였다. 수학적으로 딱 떨어지는 연역의 과정은 아닐 수도 있다..)

 

-> [1][2] + [2][5] 의 경우라면 모든 노드를 한번씩 거친 것이 최소값이 될 수도 있을 것이다.

-> 여기서 [1][2]의 최소값이 [1][5]+[5][2] 일리는 없다. 원래 [1][5]의 최소값을 구하고 있었다.;

 

-> 그래도 만약 [1][2] 의 최소값을 구하는 경로가 [1]-[5]-[3]-[2] 라면 [1][3]의 사이의 k = 5가 마지막에 반영될 수도 있지만,

([1][5][3]) + [2]  =  [1] + ([5][3][2]) 와 같을 것이기 때문에 [5]가 갑자기 마지막에 최소값 반영되어 전부 다시 해야하는 경우는 없을 것이란 결론이다. 어떤 경로가 고정되어 있으면 for문을 돔에 따라 위 괄호가 계속 바뀌어서, 누락될 염려는 없다.

 

 

import sys
from collections import deque
import heapq
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n = int(input())
m = int(input())
INF = sys.maxsize
dp = [[INF for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
	a, b, c = map(int, input().split())
	dp[a][b] = min(dp[a][b], c)

for i in range(1, n+1):
	dp[i][i] = 0

for k in range(1, n+1): # 1 2 3 4 5 
	for i in range(1, n+1):
		for j in range(1, n+1):
			dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

for i in range(1, n+1):
	for j in range(1, n+1):
		if dp[i][j] == INF:
			print(0, end=' ')
		else:
			print(dp[i][j], end=' ')
	print()