[BOJ][Python]11404 풀이

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

11404번: 플로이드

import sys
ssr = sys.stdin.readline

INF = 10000001

n = int(ssr())
m = int(ssr())
min_cost = [[INF for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, ssr().split())
    min_cost[a-1][b-1] = min(min_cost[a-1][b-1], c)
for i in range(n):
    min_cost[i][i] = 0
for middle_node in range(n):
    for start_node in range(n):
        for end_node in range(n):
            min_cost[start_node][end_node] = min(min_cost[start_node][end_node], min_cost[start_node][middle_node]+min_cost[middle_node][end_node])
for i in min_cost:
    print(*[j if j != INF else 0 for j in i])

이번에는 플로이드-워셜 최단거리 문제입니다. 데이크스트라나 벨만-포드에 비해서 상대적으로 구현이 간단하고 개념도 간단한 편입니다. 데이크스트라나 벨만-포드에 비해서 구조적 한계로 인해 시간복잡도가 높긴합니다만 한 번 쭉 구해놓고 나면 아무 노드나 2개 뽑아서 그 사이의 최단거리를 구할 수 있다는 점과, 음의 간선이 있어도 사용 가능하다는 점이 장점입니다.

 

문제에서 주의할 점은 갈 수 없는 경로의 경우 0으로 출력해야한다는 점 말고는 딱히 모르겠네요. 기초적인 플로이드-워셜 문제이니 개념을 찾아보고 이 문제로 구현 연습을 해도 좋을 것 같습니다.