[백준] 11404번: 플로이드 - 파이썬(python)

 

 

 

나의 풀이

n = int(input())
m = int(input())
dis = [[int(1e9)] * (n+1) for _ in range(n+1)]
for i in range(n+1) : 
  dis[i][i] = 0 # 자기 자신으로 가는 노선은 0
for _ in range(m) :
  a, b, c = map(int, input().split())
  dis[a][b] = min(dis[a][b], c) # a도시에서 b도시로 가는 비용 저장

for k in range(1, n+1) :
  for i in range(1, n+1) :
    for j in range(1, n+1) :
      dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

for i in range(1, n+1) :
  for j in range(1, n+1) :
    if dis[i][j] == int(1e9) :
      dis[i][j] = 0
    if j < n : 
      print(dis[i][j], end=' ')
    else :
      print(dis[i][j])

 

모든 지점에서 다른 모든 지점까지의 최단 경로를 계산하는 문제로, 전형적인 플로이드 워셜 문제이다.

플로이드 워셜은 D[a][b] = min(D[a][b], D[a][k] + D[k][b]) 의 식만 기억한다면 쉽게 풀 수 있다.

즉, a부터 b까지 가는데 1~n까지의 k를 거쳐서 가는 비용을 따져가며 최단 거리 테이블을 갱신하는 방법이다.

 

이 문제에서 다른 점은, 시작도시와 도착 도시를 연결하는 노선이 하나가 아닐 수도 있다는 점이다.

따라서, 노선을 입력받을 때 dis[a][b] 에는 항상 최솟값이 들어갈 수 있도록 min() 연산으로 비교하였다.