악곱 == 악성곱슬

플로이드

---

해당 문제는 플로이드를 한번 풀어보는 문제이다.

플로이드에 대한 설명은 따로 포스팅 해두었다.

플로이드는 다이나믹 프로그래밍을 이용한 최단 경로 구하는 방법으로, 모든 정점에서 모든 정점으로의 최당경로를 전부 구할 수 있는 알고리즘이다. O(V^3)의 알고리즘을 갖는다.

음수 사이클이 발생한다면 구할 수 없다.

해당 문제에서 함정이 하나 있는데 두 정점 사이에는 여러 간선이 존재 할 수 있다는 점이다. 따라서 입력 받을 때, min(기존, 새로운 값) 을 이용하여 초기화 하면 간단하게 응용하여 구현할 수 있다.

코드는 아래와 같다.

import sys

INF = int(1e9)

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

def solution(n, m):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == j:
                graph[i][j] = 0
    floyd(n)
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if graph[i][j] == INF:
                print(0, end=' ')
            else:
                print(graph[i][j], end=' ')
        print()

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    M = int(sys.stdin.readline().rstrip())
    graph = [[INF] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        a, b, cost = map(int, sys.stdin.readline().rstrip().split())
        graph[a][b] = min(graph[a][b], cost)
    solution(N, M)