반응형
플로이드
-
BOJ) 플로이드 (11404 번)알고리즘/백준 2021. 2. 12. 16:00
플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 모든 도시의 쌍 (A, B)에 대해서 도시 A -> 도시 B로 가는데 필요한 비용의 최솟값을 구하는 문제다. 사실, 최단거리를 보면 다익스트라를 가장 먼저 떠올렸을 것이다. 플로이드-워셜에 분류되어 있어서 플로이드-워셜 방법으로 접근을 했다. 근데, 다시 생각해보면, 모든 경로를 구해야하기 때문에, 모든 도시의 쌍 (A,B)의 거리를 다익스트라로 구한다고하면, 시간이 더욱 오래 걸릴 것 같다. 모든 도시의 쌍의 최단 거리 정보를 저장해두는 플로이드 워셜이..