[Python Algorithm] 플로이드 BOJ #11404

문제

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

11404번: 플로이드

 

내 문제 풀이

import sys
import math

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
INF = math.inf
table = [[INF for _ in range(n)] for _ in range(n)]

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().strip().split())
    table[a-1][b-1] = min(table[a-1][b-1], c)

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                table[i][j] = 0
            else:
                table[i][j] = min(table[i][j], table[i][k] + table[k][j])

for i in range(i):
    for j in range(j):
        if table[i][j] == INF:
            table[i][j] = 0

print('\n'.join(' '.join(map(str, i)) for i in table))

👉 플로이드 워셜 문제

• 3중 for문 이용, k는 중간 경로라고 설정하여 플로이드 워셜 알고리즘을 이용했다.
• 출발 지점과 도착 지점이 같은 경우는 없으므로 i == j 의 경우 0을 넣어주었다.
• 그 외의 경우에는 기존의 값과 k를 거칠 경우의 값 중 더 싼 값을 찾아 대체했다.

+ 이 문제처럼 최솟값을 업데이트해주어야 하는 경우, 처음 변수를 어떤 값으로 초기화할지 결정하기 어렵다.

제일 클 것으로 예상되는 최솟값보다는 더 큰 값으로 설정해주어야 하기 때문이다.

하지만 위와 같이 math.inf 를 사용해주면 무한대 값으로 초기화할 수 있으므로 편리하다.

 

💡 피드백

• 출발 지점과 도착 지점이 같은 경우만 잘 예외처리해주면 되는 문제 !
  플로이드 워셜 알고리즘을 사용하는 가장 기본적인 예제인 것 같다.