백준_11404_플로이드
https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작
www.acmicpc.net
해결 방법
>문제가 모든 도시에서 갈 수 있는 도시까지의 최소거리를 구하는 문제이다.
>문제의 제목에서 알 수 있듯이 플로이드 알고리즘을 이용하면 된다.
>도시에서 도시까지의 비용이 여러개 입력되므로 그 중 최솟값을 구한다.
>갈 수 없는 경로는 0을 출력한다.
플로이드 알고리즘 참고 자료
플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다.[1][2] 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 R
ko.wikipedia.org
코드
import sys
input = sys.stdin.readline
num_city = int(input())
num_bus = int(input())
city_info = dict()
min_fare = [[float('inf') for i in range(num_city)]for i in range(num_city)]
'''
플로이드 알고리즘을 위한 2차원 배열 만드는 부분
이번 문제의 입력 중 도시에서 도시로 가는 비용이 여러개 입력되므로
그 중 최솟값을 찾기 위해 그래프를 이용하였다.
'''
for i in range(1, num_city + 1):
city_info[i] = dict()
for i in range(1, num_city+1):
for j in range(1, num_city+1):
city_info[i][j] = list()
city_info[i][j].append(0)
if i == j:
min_fare[i - 1][j - 1] = 0
for i in range(num_bus):
departure, arrival, fare = map(int, input().split())
city_info[departure][arrival].append(fare)
#여러개의 비용 중 최솟값 찾기
def _min(input_list):
if len(input_list) == 1: #이어지지 않은 부분 -> float('inf')
return float('inf')
input_list.remove(0)
return min(input_list)
for i in range(1, num_city+1):
for j in range(1, num_city+1):
if i == j:
continue
min_fare[i - 1][j- 1] = _min(city_info[i][j])
#플로이드 워셜 알고리즘
for k in range(num_city):
for i in range(num_city):
for j in range(num_city):
if i == j:
continue
else:
min_fare[i][j] = min(min_fare[i][k] + min_fare[k][j], min_fare[i][j])
#출력
for i in min_fare:
for j in i:
if j == float('inf'): #문제에서 갈 수 없는 도시는 0으로 표시하라고 함
print(0, end = " ")
else:
print(j, end = " ")
print()