[최단경로] 플로이드

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 20분

1. 문제 설명

- 플로이드 워셜 알고리즘 구현 문제

2. 접근 방식

- 플로이드 워셜 알고리즘을 사용

- 단, 입력을 받을 때도, 동일한 위치에 cost값이 변형 될 수 있기에 조건을 넣어줘야 한다. (처음에 이 부분을 안 넣어서 오류가 났었음)

3. 코드

import sys

n = int(input())
m = int(input())
INF = 1e9
graph = [[INF]*(n+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0
input = sys.stdin.readline
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = min(graph[a][b], c)
    
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print(0, end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

4. 코멘트

- 백준에서는 최단경로 문제처럼 그래프 형태를 입력으로 받는다면, import sys.stdin.readline() 기억하자, [readline's'아님)