[Python] 백준 11404 플로이드 | 플로이드 워셜

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

11404번: 플로이드

 

 

문제 해결 포인트

- 플로이드 워셜 알고리즘

- graph : 2차원 배열로 노드 별 각 노드까의 최소 거리를 저장한다. graph[i][j] 는 i에서 j로 가기 위한 최소 이동 거리를 의미함

- 각 간선 정보를 따라 무한수(INF)로 초기화 한 graph를 수정한다. 동일한 노선의 길이가 다른 간선이 있음으로 주의 필요

- a -> b 노선에 대해서 k를 거쳐가는 경우와 비교하여 작은 값으로 업데이트 한다.

   a = b라면 거리는 0이다.

 

- 3중 for문 종료 후 각 노드에 대해 최고 길이가 저장된 graph를 노드 1부터 출력하면 끝!

 

 

작성 코드

 

import sys
input = sys.stdin.readline
INF = int(1e9)

n = int(input())
m = int(input())
graph = [[INF]*(n+1) for _ in range(n+1)]  # 인접 행렬

for _ in range(m):
    v1, v2, w = map(int, input().split())
    graph[v1][v2] = min(graph[v1][v2], w)  # (주의) 동일한 노선의 간선 있음

for k in range(1, n+1):  # 거쳐갈 노드
    for a in range(1, n+1):  # 시작 노드
        for b in range(1, n+1):  # 종료 노드
            # (a -> k -> b) 와 (a -> b) 비교하여 작은 값 대입
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) if a != b else 0

for i in range(1, n+1):
    for j in range(1, n+1):
        print(graph[i][j] if graph[i][j] != INF else 0, end=" ")  # INF라면 0 출력
    print()

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

---

REFERENCE

https://claude-u.tistory.com/334