[백준] 플로이드

https://www.acmicpc.net/problem/11404

11404번: 플로이드

플로이드-워셜 알고리즘을 사용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

n개의 도시를 잇는 m개의 버스가 존재합니다. 이때, 버스들은 출발지, 목적지, 가는비용을 가지고, 출발지와 목적지가 같은 버스는 존재하지 않을 때, 특정한 도시를 출발하여 특정한 도시에 도착하는 최소 비용을 구해야 하는 문제입니다. 

이 때, 이동이 불가능한 경우에는 0을 출력해야 합니다.

 

<Solution>

이 문제는 전형적인 플로이드-워셜 알고리즘을 사용하는 문제입니다. (출발지가 한 노드인 경우 다익스트라 알고리즘을 사용하지만 모든 출발지에 대해 모든 도착지로의 최소 비용을 구해야하면, 플로이드 워셜 알고리즘을 주로 사용합니다. 물론 시간 복잡도가 node^3으로 크기에 주의해서 사용해야 합니다.)

 

주의해야 하는점은 a라는 출발지에서 b라는 도착지로 가는 버스의 종류가 여러개가 있을 수 있으므로, 인접 행렬을 구성하는 과정에서 최소의 cost로 가는 버스들만 남겨야 합니다.

 

실제 구현은 아래와 같습니다.

import sys

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())

# bus info
buses = [[int(2e9)]*(n+1) for _ in range(n+1)]
for _ in range(m):
    start, end, cost = list(map(int,sys.stdin.readline().rstrip().split()))
    if buses[start][end] > cost:
        buses[start][end] = cost

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

for k in range(1,n+1): # 거쳐가는 node
    for i in range(1,n+1): # 출발 node
        for j in range(1,n+1): # 도착 node
            if buses[i][k] + buses[k][j] < buses[i][j]:
                buses[i][j] = buses[i][k] + buses[k][j]

for bus in buses[1:]:
    bus_ = list(map(str, [0 if e == int(2e9) else e for e in bus[1:]]))
    print(' '.join(bus_))