[BOJ/백준] 11404 플로이드

import sys

input = sys.stdin.readline
n = int(input())
INF = float('inf')
graph = [[INF if i !=j else 0 for j in range(n)] for i in range(n)]
m = int(input())

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 start in range(n):
        for end in range(n):
            if graph[start][end] > graph[start][k] + graph[k][end]:
                graph[start][end] = graph[start][k] + graph[k][end]



for row in graph:
    print(*[j if j != INF else 0 for j in row])

플로이드 와샬을 이용한 문제였다.

 

2차원 배열을 자기자신을 가는 경우를 제외한 나머지 경우를 INF로 초기화 시켜주고, 들어오는 input에서도 같은 경로를 여러번 들어오는 경우가 있으므로, 최소값으로 넣어주었다.

 

그리고 플로이드 와샬을 3중 for문으로 구현해줬다.

 

출력은 if else문을 이용해 INF가 그대로인 곳은 갈수 없는 곳이므로 0으로 출력해주었다.