[Baekjoon Online Judge] 백준 11404번 플로이드(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 11404번 플로이드

(Python)

(글쓴날 : 2020.06.12)

 

---

* Baekjoon Online Judge, 백준 11404번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 11404번 플로이드

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/11404

11404번: 플로이드

---

2) 풀이 과정

* 시간 복잡도 : O(EV²)

 

n개의 도시와 각 도시별 버스 노선 금액이 주어질 때, 모든 도시의 쌍(A, B)에 대해 A에서 B로 가는데 필요한 최소 비용을 구하는 문제입니다.

단, 시작 도시와 도착 도시가 같은 경우는 없으며, 각 도시를 연결하는 노선이 하나가 아닐 수 있습니다.

 

저의 경우, 플로이드 와샬 알고리즘을 적용하였고, Python을 사용했습니다.

주어지는 정보 중 같은 경로가 주어질 시 최소 금액을 기록해야 하는 것을 고려하여 인접 행렬을 구현한 뒤, 플로이드 와샬 알고리즘을 적용해 모든 도시의 각 도시별 최소 비용을 구하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
def floydWarshall():
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
n = int(input())
m = int(input())
INF = 2147483647
dist = [[0] * n] + [[0] + [INF] * n for _ in range(n)]
 
for i in range(1,n+1):
    dist[i][i] = 0
 
for _ in range(m):
    a,b,c = map(int,input().split())
 
    dist[a][b] = min(dist[a][b], c)
 
floydWarshall()
 
for i in range(1,n+1):
    for j in range(1,n+1):
        print(dist[i][j] if dist[i][j]!=INF else 0, end=" ")
    print()

---