[백준] 11404번 플로이드 - Python

이번에 해결해 볼 문제는 백준에 있는 플로이드이다.

---

문제 설명

1. n개의 도시 (0 <= n <= 100)
2. 한 도시에서 출발하여 다른 도시에 도착하는 m(1 <= m <= 100,000)개의 버스가 있다.
3. 각 버스는 한 번 사용할 때 필요한 비용이 있다.
4. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하면 된다.

문제 아이디어

• 출발 도시가 정해져 있지 않고 모든 도시 간의 최소 비용을 구하는 문제이므로 플로이드-워셜 알고리즘을 사용한다.

나의 실수

• 도시 간의 최솟값을 구하기 위해 초기값으로 문제에서 나올 수 있는 최댓값을 도시간의 비용 초기값으로 설정해야 한다.
  • (n-1)*100,001 또는 int(1e9)
  • 처음에 100,001으로 초기화하여 틀렸었다.

문제 해결 코드

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

MAX = int(1e9) # n개의 도시가 있으므로 최대 (n-1)*100001
graph = [[MAX]*n for _ in range(n)]
for i in range(n):
    graph[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = min(graph[a-1][b-1], c)

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

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