백준 - 플로이드(11404)

문제 링크 ▶︎ 백준 플로이드 11404

문제 전략

이 문제는 최단 거리 경로 알고리즘 중 플로이드 워셜 알고리즘 문제이다.

다익스트라의 경우 한 지점에서의 최단 경로를 구하는 알고리즘이지만, 플로이드 워셜 알고리즘은 모든 지점에서의 최단 경로를 구할 때 쓰는 알고리즘이다.
소스 코드는 다익스트라보다 쉬웠다.

우선 입력을 2차원 배열로 받고, i번 도시 -> j번 도시 이동 비용을 bus[i][j]에 저장한다.
또한 중복이 있기 때문에 비용은 최솟값을 저장한다.

이후 3중 반복문을 돌면서 중간에 k번 도시를 거쳐서 이동했을 때와 비교하면서 항상 최솟값을 갱신하게 해준다.
그리고 만약 i번 도시에서 j번 도시로 가는 경로가 없다면 INF 가 갱신되지않고 그대로 있기 때문에 INF 라면 0으로 바꿔준다.

코드

import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
INF = 987654321
bus = [[INF] * (n+1) for _ in range(n+1)]
for i in range(1,n+1):
    bus[i][i] = 0
for _ in range(m):
    a,b,c = map(int,input().split())
    bus[a][b] = min(bus[a][b],c)

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

for row in bus[1:]:
    for i in range(1,n+1):
        if row[i] == INF:
            row[i] = 0
    print(*row[1:])

개선 사항

코드 자체는 다익스트라보다 간단한듯, 하지만 좀 더 연습이 필요할듯.