BaekJoon 11404번 : 플로이드 (python)

BaekJoon 11404번 : 플로이드 (G4 41.855%)

주어진 문제에서는 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성해야 한다.
이번 문제 같은 경우는 최단 경로를 구하는 알고리즘 중 플로이드 워셜 알고리즘을 사용하는 문제이다.
즉 주어진 도시의 개수가 N개라면 i번째 줄에 0~N개까지의 최단 경로를 i가 0~N범위에서 구하는 문제인 것이다.

• 플로이드 워셜 알고리즘

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.
• 플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.
  • 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.
• 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.
• 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다.

• 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.
  • a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.
• Distance[a -> b] = min(Distance[a -> b], Distance[a - > k] + Distance[k -> b])

import sys
input = sys.stdin.readline
INF = 1e10

N = int(input())
M = int(input())
distance = [[INF]*(N+1) for _ in range(N+1)]
for i in range(1,N + 1) :
    distance[i][i] = 0

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

for k in range(1,N+1) :
    for a in range(1, N+1) :
        for b in range(1, N+1) :
            distance[a][b] = min(distance[a][b], distance[a][k] + distance[k][b])

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