해당 문제는 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
'Algorithm > Dynamic Programming' 카테고리의 다른 글
[백준] 26156: 나락도 락이다 (python 파이썬) (0) | 2023.03.13 |
---|---|
[백준] 12865: 평범한 배낭 (python 파이썬) (0) | 2022.11.21 |
[백준] 11049: 행렬 곱셈 순서 (python 파이썬) (0) | 2022.11.12 |