[ 백준 11404 ] 플로이드 - Python

문제 보기

이 문제는 플로이드 와샬(Floyd Warshall) 문제 이다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하면 된다. 하나의 경로가 아닌 모든 경로를 구해야하기 때문에 플로이드 와샬이 적합하다. 사실 문제 이름을 통해서 플로이드 와샬을 유추할 수도 있다..!

 

플로이드 와샬을 구현하는 것은 어렵지 않으나, 3중 for문이기 때문에 n값이 작을때만 가능하다는 점을 유의해야 한다.

 

i에서 j로 가는 비용과 i에서 k를 거치고 j로 가는 경우를 계속해서 비교하면 된다.

for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])

 

코드

import sys


if __name__ == "__main__":

    # inputs
    N = int(input())
    M = int(input())
    bus = [list(map(int, input().split())) for _ in range(M)]

    d = [[sys.maxsize] * N for _ in range(N)]

    # initial
    for row, col, cost in bus:
        d[row - 1][col - 1] = min(d[row - 1][col - 1], cost)
    for i in range(N):
        d[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    for i in range(N):
        for j in range(N):
            if d[i][j] == sys.maxsize:
                d[i][j] = 0

    for i in range(N):
        print(" ".join(map(str, d[i])))