백준 1507 C1

• 

  [백준] 1507번 궁금한 민호 C 해설 (플로이드 와샬 - reverse) 출처 : https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간 (≤ 10,000)이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 필요한 시간은 0이다. www.acmicpc.net 그리디, 플로이드 와샬 알고리즘으로 분류된 문제이다. 플로이드 와샬 알고리즘으로 분류되어 있길래 당황했지만 신기한 접근으로 풀어나가는 문제여서 천천히 풀어보았다. 당황했던 이유는 이미 모든 노드로 가는 최단경로를 입력으로 주어졌기 때문이었다. 하지만 이 문제는 플로이드 와샬 알고리즘을 역으로 이용하는 문제였다... 프로그래밍/Algorithm 2019. 10. 8.