[baekjoon] 백준 11404번(파이썬): 플로이드

문제

11404번: 플로이드

알고리즘

- 처음에 dfs를 통해 문제를 해결하려 했지만 문제 이름과 같이 플로이드 문제였다.

- 반복문을 통해 경로를 확인하고 한 번에 가는 경우와 중간에 거쳐서 가는 경우를 비교/계산한다.

코드

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[1e9 for _ in range(n + 1)] for _ in range(n + 1)]

# 자기 자신으로 오는 경우는 x
for _ in range(n + 1): graph[_][_] = 0

# 반복문을 통해 그래프를 표시
for _ in range(m):
    s, e, c = map(int, sys.stdin.readline().split())
    if graph[s][e] > c:
        graph[s][e] = c

# 반복문을 통해 경로 확인
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):

            # 자기 자신으로 오는 경우는 x
            if j == k:
                graph[j][k] = 0

            # j -> k 로 가는 경우와 j -> i -> k 로 가는 경우중 비용이 적게드는 것을 확인
            else:
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

# 반복문을 통해 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == 1e9:
            print(0, end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법