[백준/Java] 1854 K번째 최단경로 찾기

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

문제 요약

여행할 도시의 개수 n과 도시 간에 존재하는 도로의 수 m이 있다.
1번 도시에서 i번 도시로 가는 k번째 최단 경로의 소요 시간을 얻고자 한다.

"a b c": a 도시에서 b 도시로 갈 때 c 시간이 걸린다.
도시의 개수 n은 최대 1000이다.
도로의 개수 m은 최대 2백만이다.
k는 최대 100이다.
각 도로를 지나는 데 걸리는 시간 c는 최대 1000의 자연수이다.
최단 거리에 같은 정점이 여러 번 포함되어도 된다.

---

문제 접근

하나의 정점에서 다른 정점까지의 거리를 구하는 문제이며, 음수 가중치가 존재하지 않기 때문에 다익스트라 알고리즘을 사용한다.
각 정점에 대해 가장 짧은 거리가 아니라, k번째로 짧은 거리까지 기록하도록 하면 된다.
이러면 다익스트라가 안 끝난다고 생각할 수도 있는데, k번째로 짧은 거리보다 큰 경우에는 더 탐색을 하지 않도록 하면 되기 때문에 괜찮다.

정점의 번호는 1부터 시작하니까 편의를 위해 사용하는 자료구조의 크기를 n+1로 설정한다.

---

풀이

기본적인 아이디어는 다음과 같다.

1. (추가 예정)

이를 구현한 코드는 다음과 같다.

import java.util.*;
import java.io.*;

public class Main {
	
	static int n, m, k;
	static ArrayList<int[]>[] graph;
	
	static PriorityQueue<Integer>[] distance;
	
	public static void getInput() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		/// n, m, k 입력 받기
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st1.nextToken());
		m = Integer.parseInt(st1.nextToken());
		k = Integer.parseInt(st1.nextToken());
		
		// 그래프 초기화
		graph = new ArrayList[n+1];
		for (int i = 0; i < n+1; i++) {
			graph[i] = new ArrayList<>();
		}
		
		// 그래프 입력 받기
		for (int i = 0; i < m; i++) {
			StringTokenizer stm = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(stm.nextToken());
			int b = Integer.parseInt(stm.nextToken());
			int c = Integer.parseInt(stm.nextToken());
			
			int[] nextNode = new int[] {b, c};
			graph[a].add(nextNode);
		}
		
		// 정답 기록 우선순위 큐 초기화
		// 거리의 내림차순으로 설정한다. 크기가 최대 k가 되도록 한다.
		distance = new PriorityQueue[n+1];
		for (int i = 0; i < n+1; i++) {
			distance[i] = new PriorityQueue<>(Collections.reverseOrder());
		}
	}
	
	// 다익스트라 알고리즘을 이용하여 문제 해결
	public static void findKthPath() {
		// 시간의 오름차순으로 정렬되는 우선순위 큐
		PriorityQueue<int[]> search = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[1], o2[1]);
			}
		});
		
		// 시작점을 큐에 넣음
		int[] start = new int[] {1, 0};
		search.add(start);
		distance[1].add(0);
		
		// 해당 정점의 k번째 최단 거리 찾기
		// next의 거리 큐(distance)에 이미 k개가 있으며, 지금 구한 값이 거리 큐의 머리보다 크면 탐색 큐(search)에 넣지 않는다.
		// 만약 그 거리 큐의 머리보다 작다면 머리를 빼내고 그 값을 넣는다. 탐색 큐에도 넣어서 더 탐색한다.
		while (!search.isEmpty()) {
			int[] now = search.poll(); // {노드 번호, 시작점과의 거리}
			
			for (int[] next : graph[now[0]]) { // {노드 번호, now[0]와의 거리}
				// 거리 큐의 크기가 k보다 작다면 거리 큐에도 넣고, 탐색 큐에도 넣음
				if (distance[next[0]].size() < k) {
					distance[next[0]].add(now[1]+next[1]);
					int[] updatedNext = new int[] {next[0], now[1]+next[1]};
					search.add(updatedNext);
				}
				// 거리 큐의 크기가 k라면 peek해서 값을 확인하고 처리함
				else {
					// 거리 큐의 peek과 같거나 크다면 넘어감
					if (now[1]+next[1] >= distance[next[0]].peek()) {
						continue;
					}
					// 거리 큐의 peek보다 작다면 거리 큐를 수정하고 탐색 큐에도 넣음
					else {
						distance[next[0]].poll();
						distance[next[0]].add(now[1]+next[1]);
						int[] updatedNext = new int[] {next[0], now[1]+next[1]};
						search.add(updatedNext);
					}
				}
			}
		}
	}
	
	// 정답 정리 및 출력
	public static void printAnswer() {
		StringBuilder sb = new StringBuilder();
		
		for (int i = 1; i < n+1; i++) {
			if (distance[i].size() < k)	sb.append(-1+"\n");
			else sb.append(distance[i].peek()+"\n");
		}
		
		System.out.println(sb);
	}
	
	public static void main(String[] args) throws IOException {
		// 입력 받기
		getInput();

		// 다익스트라 알고리즘을 이용하여 문제 해결
		findKthPath();

		// 정답 정리 및 출력
		printAnswer();
	}
}

---

회고

(추가 예정)