백준 11780. 플로이드 2
https://www.acmicpc.net/problem/11780
11780번: 플로이드 2
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
상당히 어렵지만 의미 있는 문제였다.
이 문제에서 플로이드와샬 알고리즘을 이용해서 최단거리를 구하고, 경로도 구하는 방법을 알게 됐다.
출력은 크게 두가지를 요구하는데 첫번째는 모든 도시 쌍의 최단거리를 구하는 것이고,
두번째는 최단거리로 이동했을때 거쳐가는 노드들을 모두 출력하는 것이다.
첫번째는 그냥 플로이드와샬을 돌리면 해결된다.
핵심은 두번째인데 지금까지 플로이드 와샬로 푸는 문제들은 단순히 거리를 출력하면 됐었지만 이 문제는 경로까지 출력해야 한다.
경로를 출력하는 방법은 플로이드 와샬을 돌릴때 i -> j 로 이동할때 거쳐가는 k 를 저장해 놓는 것이다.
예를들어 i -> j 로 갈때 k를 거쳐가는 것이 최단 거리라면 midNode[i][j] = k 이런식이다.
이렇게 중간경로를 저장해놓으면 재귀적으로 해결할수 있다.
예제의 2 -> 3 의 경로를 출력한다고 해보자.
플로이드와샬을 돌린 후 midNode[][]는 다음과 같다
0 0 0 0 3
5 0 5 0 4
0 5 0 0 0
5 5 5 0 0
0 0 1 2 02 -> 3
2->5 5->3
2->4 4->5 5->1 1->3
이런식으로 2->3의 중간은 5이기 때문에 2->5, 5->3 으로
2->5는 4이기 때문에 2->4, 4->5 이렇게 재귀적으로 생각해볼수 있다.