[Python] G4_11404_플로이드 🚌

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

문제

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

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

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

예제

조건

• 시간 제한: 1초
• 메모리 제한: 256MB

import sys
input = sys.stdin.readline
INF = sys.maxsize
# Input
V = int(input())
E = int(input())
dp = [[INF]*V for _ in range(V)]
for i in range(V):
    dp[i][i] = 0
# 초기 노선 정보를 저장
for _ in range(E):
    u,v,w = map(int,input().split())
    if dp[u-1][v-1] == INF:
        dp[u-1][v-1] = w
    # 중복된 정보일 경우, 더 작은 값을 넣어줌
    else:
        dp[u-1][v-1] = min(dp[u-1][v-1],w)
# 플로이드-워셜 알고리즘   
for k in range(V):
    for i in range(V):
        for j in range(V):
            if dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]
# Output                
for row in dp:
    for i in range(V):
        # 갈 수 없는 경우
        if row[i] == INF:
            row[i] = 0
    print(*row)

이 문제는 노드와 노드 간 최단 거리를 구할 수 있는 플로이드-워셜 알고리즘을 사용해야 하는 문제이다.

• 노드의 개수 V, 간선의 개수 E, 노드 간 최단 거리를 저장할 dp 를 설정한다.

• 본인에서 본인으로의 거리는 0이기에 0을 저장해준다.
  for i in range(V): dp[i][i] = 0

초기 노선 정보를 저장해준다.

• 입력은 1부터 들어오기에, -1씩 한 상태로 가중치를 넣어주어야 한다.

• 또한, 시작 노드와 도착 노드가 같은 간선이 들어올 수 있기 때문에, 가중치가 더 작은 값으로 넣어주어야 한다.

플로이드-워셜 알고리즘을 실행한다.

• k는 중간에 거쳐서 갈 노드, i는 시작 노드, j는 도착 노드를 의미한다.

• 즉 i에서 j로 바로 가는 것보다, k를 중간에 한 번 거쳐서 가는 것이 더 가중치가 적다면 그 값으로 변경해주는 것이다.

• if dp[i][j] > dp[i][k] + dp[k][j]: dp[i][j] = dp[i][k] + dp[k][j]

최종적으로 결정된 노드 간의 최단 거리(=가중치)를 출력해준다.

• 노드 간 이동이 불가해, 여전히 INF값이 들어있는 경우가 있으므로 이 때는 0으로 변경해서 출력해준다.

느낀 점 & 배운 점

1. 플로이드-워셜 알고리즘을 처음 사용해보았는데, 어려워보였지만 생각보다 간단한 구조라서 쉽게 활용할 수 있었다.

2. 당분간은 비슷한 문제를 풀면서 습득해나갈 예정이다!