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

해당 문제는 Floyd Warshall 알고리즘을 사용해 풀 수 있는 문제다. Floyd Warshall 알고리즘은 a에서 b도시로 이동하는 최단 거리를 임의의 도시 c를 경유하는 모든 경우를 고려하여 구하는 알고리즘이다. 즉, 총 도시의 개수가 5개인 경우 1에서 2로 이동하는 최단 거리를 찾을 때 아래 경우를 모두 고려한다.

• 도시 1에서 도시 1로 이동 후 도시 1에서 도시 2로 이동
• 도시 1에서 도시 2로 이동 후 도시 2에서 도시 2로 이동
• 도시 1에서 도시 3로 이동 후 도시 3에서 도시 2로 이동
• 도시 1에서 도시 4로 이동 후 도시 4에서 도시 2로 이동
• 도시 1에서 도시 5로 이동 후 도시 5에서 도시 2로 이동

해당 알고리즘은 DP을 활용하여 다음과 같이 구현할 수 있다.

 

import sys
input = sys.stdin.readline
INF = float("inf")

city_num = int(input())	# city_num: 도시 개수
bus_num = int(input())  # bus_num: 버스 개수
results = [[INF for _ in range(city_num)] for _ in range(city_num)] # results[a][b]: 도시a에서 도시b로 가는데 드는 최소 비용

# 도시a에서 도시a로 이동하는 버스는 없으며 해당 비용은 0이다.
for city in range(city_num):
    results[city][city] = 0

# 모든 버스의 정보를 입력받는다.
for _ in range(bus_num):
    start_city, end_city, cost = map(int, input().split())
    results[start_city-1][end_city-1] = min(results[start_city-1][end_city-1], cost)

# start_city에서 end_city로 가는데 mid_city를 경유하는 경우를 탐색한다.
for mid_city in range(city_num):
    for start_city in range(city_num):
        for end_city in range(city_num):
            tmp = results[start_city][mid_city]+results[mid_city][end_city]
            results[start_city][end_city] = min(results[start_city][end_city], tmp)

# 문제의 요구대로 갈 수 없는 경우(값이 INF인 경우)는 값을 0으로 넣어준다.
for result in results:
    for i in range(city_num):
        if result[i] == INF:
            result[i] = 0

# 모든 결과를 출력한다.
for result in results:
    print(*result)

 

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

11404번: 플로이드