(Python) - BOJ(11404번) : 플로이드

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

11404번: 플로이드

---

• 문제 : 

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

 

 

 

 

---

• 풀이 :

플로이드-와샬 알고리즘을 적용하여 해결할 수 있는 문제였습니다. 

 

플로이드-와샬 알고리즘이란 한 정점에서 다른 모든 정점으로의 최단거리를 구할 수 있는 BFS와 달리 

모든 정점에서부터 다른 모든 정점으로 가는 최단거리를 구할 수 있는 알고리즘입니다.

기본적인 아이디어는 

 

출발지 i, 도착지 j가 있을 때 i와 j를 제외한 나머지 모든 정점(경유지)를 k라고 하겠습니다.

3중 for문을 이용하여 i -> j로 바로 가는 경우와 i -> k -> j의 k를 경유하여 j로 가는 경우 중 코스트가 낮은 방법으로 초기화해주면 됩니다. 

3중 for문을 사용하여 시간복잡도는 O(V^3)입니다. V는 정점의 개수입니다.

 

cost = [[float("inf")]*N for _ in range(N)]

for k in range(N):  # 경유지
    for i in range(N): # 출발지
        for j in range(N): #도착지
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

 

위 코드는 플로이드 와샬 알고리즘의 기본 코드입니다. N은 정점의 개수이며, 이 사이에 정점 사이의 가중치가 주어집니다.

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
cost = [[float("inf")]*N for _ in range(N)]
for _ in range(M):
    A,B,C = map(int,input().split())
    cost[A-1][B-1] = min(cost[A-1][B-1], C)

for k in range(N):  # 경유지
    for i in range(N): # 출발지
        for j in range(N): #도착지
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

for i in range(N):
    ans = []
    for j in range(N):
        if i == j or cost[i][j] == float("inf"):
            ans.append(0)
        else:
            ans.append(cost[i][j])
    print(" ".join(map(str,ans)))