BOJ 1854 K번째 최단경로 찾기

https://www.acmicpc.net/problem/1854

1854번: K번째 최단경로 찾기

문제

봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작성해 보자.

입력

첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1,000, 0 ≤ m ≤ 2,000,000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.

이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 a, b, c가 포함되어 있다. 이것은 a번 도시에서 b번 도시로 갈 때는 c의 시간이 걸린다는 의미이다. (1 ≤ a, b ≤ n, 1 ≤ c ≤ 1,000)

도시의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 도시는 시작도시이다. 두 도로의 시작점과 도착점이 모두 같은 경우는 없다.

출력

n개의 줄을 출력한다. i번째 줄에 1번 도시에서 i번 도시로 가는 k번째 최단경로의 소요시간을 출력한다.

경로의 소요시간은 경로 위에 있는 도로들을 따라 이동하는데 필요한 시간들의 합이다. i번 도시에서 i번 도시로 가는 최단경로는 0이지만, 일반적인 k번째 최단경로는 0이 아닐 수 있음에 유의한다. 또, k번째 최단경로가 존재하지 않으면 -1을 출력한다. 최단경로에 같은 정점이 여러 번 포함되어도 된다.

 

풀이

n=1일때는 자명하게 다익스트라로 구할 수 있다. 다익스트라로 1번째 최단경로를 구하는 과정을 다시 곱씹어보자.

이때까지의 모든 방문에 대해 방문하지 않은 모든 정점을 방문하고, 1번째 최단경로를 갱신한다. 이를 적절히 변형해서 k번째까지 구하면 된다.

우선순위 큐에는 아직 갱신되지 않은 적절한 경로들이 들어있다고 하자. 우선순위 큐의 정렬 순서는 경로의 길이이다. 우선순위 큐에서 경로 하나를 pop하자. 이 경로의 최종 정점에 인접한 모든 정점들로 가는 전체 경로들을 우선순위 큐에 넣자. 이렇게 되면 각 최종 정점으로 가는 새로운 경로가 생긴다. 이때 최종 정점 중 한 번 이상 방문한 경우 우선순위 큐에 넣는 과정을 생략하면 1번째 최단경로를 다익스트라를 이용해 구할 수 있다.

 

일정 횟수 이상 방문을 제한하는 것으로 k번째 최단경로도 쉽게 구할 수 있다. 위 과정에서 방문 횟수가 k 미만인 경우 우선순위 큐에 넣고, k 이상인 경우 넣지 않는 것으로 충분하다.

먼저, 1번 정점으로 가는 길이 0의 경로를 우선순위 큐에 넣고 시작하자. 반복문을 통해 우선순위 큐에서 경로 하나를 pop한다. 그리고 이 정점의 방문횟수를 추가한다. 이 방문횟수는 이 경로가 몇 번째 최단경로인지를 의미한다. 이 정점과 연결된 모든 k번 미만 방문한 정점에 대해 이 경로 뒤에 그 정점을 추가해 우선순위 큐에 집어넣는다. 

 

이 로직의 정당성은 아래 과정을 통해 보일 수 있다.

1. 경로를 우선순위 큐에 넣고 순서대로 탐색했기 때문에, 정점을 방문할 때 사용한 경로 가운데 k번째 경로를 반환한다.

2. 누락되는 경로는 없다. 만약 존재한다면, 다시말해 적절한 시점에서 우선순위 큐의 경로 길이 length에 대해 우선순위 큐에 한 번도 들어가지 않은 경로 중 length보다 작은 길이의 경로 P가 존재한다면, P의 마지막 정점을 제거한 P-가 우선순위 큐에 들어간 적이 없다는 것이고, P--도 우선순위 큐에 들어간 적이 없다는 것이고, ... 의 과정을 통해 모순을 반환할 수 있다. (1번 정점으로 가는 길이 0의 경로를 넣은 적 없다는 결론을 얻을 수 있으므로)

3. k번을 초과하여 정점 A를 방문한 뒤 B를 방문하는 경로는 B를 k번 이하 방문하는 경로일 수 없다. A를 방문한 뒤 B를 방문하는 k개의 경로가 더 짧은 경로가 되기 때문이다.

 

마지막으로 경로의 모든 과정을 우선순위 큐에 넣을 필요는 없다. 따라서 경로의 길이와 최종 방문한 정점만 우선순위 큐에 넣는 것으로 해결가능하다.