2/5 Coding Test

✅ Coding Test

🎈 11404 플로이드

n개의 도시가 있고 한 도시에서 출발해 다른 도시에 도착하는 m개의 버스가 있을 때 각 버스는 한 번 사용 시 일정 비용을 지불해야 한다.
모든 도시 쌍 A -> B로 이동 시 필요한 비용의 최솟값을 구하는 문제.

첫 줄에 N, 둘째 줄에 M, 셋째 줄부터 M+2줄까지 버스 정보가 주어진다.
버스 정보의 경우 출발 도시, 도착 도시, 필요한 비용으로 주어지고 비용은 100,000보다 작거나 같은 자연수이다.

출력값으로는 n줄만큼 i->j번째 도시로 가는데 필요한 최소 비용을 출력하는 문제

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
graph = [[1e9]*(n+1) for _ in range(n+1)]
# 자기 도시로 간 것은 0
for i in range(1, n+1):
    graph[i][i] = 0
# m줄만큼 입력값 처리 (단, 같은 목적지가 있을 수 있으니 append가 아닌 min값 비교)
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = min(graph[a][b], c)

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

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

< 해설 >

O(N^3)의 복잡도를 갖는 플로이드 워셜 문제
정리하면 i, j, k 순으로 for loop를 돌되 j를 출발해 k로 가는 경로 중 최소 비용을 구하면 된다. 단 경로가 1개만 있는 것이 아니므로, 기존 append가 아닌 min으로 최솟값을 비교해주어야 한다.
주의할 점은 경로의 기준 즉, 경유지가 되는 i를 가장 위에 두고 j->k와 j->i->k를 비교해 더 최소 비용이 발생하는 경로를 선택하면 된다.