1854. K번째 최단경로 찾기

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

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

문제

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

입력

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

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

도시의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 도시는 시작도시이다.

출력

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

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

LOGIC

1. 1번 도시에서 i번 도시로 이동하는 것이므로 유향그래프로 입력받는다.
2. 다익스트라 알고리즘을 이용하지만 기존과 다르게 최단거리 뿐만 아니라 갈 수 있는 모든거리를 구한다. 단, 경우의 수가 K개를 넘으면 가장 큰값과 비교하여 삽입, 삭제를 한다.
3. i번째로 갈 수 있는 경우의 수가 K개를 넘지 않으면 -1, K개면 K번째 값을 출력한다.

이동가능한 도시의 정보를 인접리스트를 사용하여 유향 그래프로 입력받는다.

for (int i = 0; i < M; i++) {
	st = new StringTokenizer(br.readLine());
	
	int from = Integer.parseInt(st.nextToken());;
	int to = Integer.parseInt(st.nextToken());;
	int weight = Integer.parseInt(st.nextToken());;
	
	cities[from].add(new Vertex(to, weight));
}

 

다익스트라 알고리즘을 이용하여 최단거리를 구하지만 우리는 K번째 최단거리가 필요하기 때문에

i번째 도시로 갈 수 있는 모든 경우의 수 중 K번째를 구해야 한다.

그래서 보통의 다익스트라와 다르게 누적된 거리가 크다고해서 다음 정점으로 넘어가지 않는다.

아래 코드는 본문과는 상관없고 다익스트라에서 필요하지 않은 부분을 보여주기 위한 코드이다.

while(!q.isEmpty()) {
	Vertex vt = q.poll();
	
	/////////////////////////////////////
	//이 if문 부분이 필요하지 않다
	if(vt.weight > D[vt.to]) continue;
	/////////////////////////////////////
	
	for (Vertex v : adjList[vt.to]) {
		long cost = D[vt.to] + v.weight;
		
		if(D[v.to] > cost) {
			D[v.to] = cost;
			q.add(new Vertex(v.to, cost));
		}
	}
}

 

그래서 우리는 갈 수 있는 모든 정점들을 살펴보며 누적된 거리를 PriorityQueue에 내림차순으로 넣으며 Size를 K와 비교하여 K보다 작으면 그냥 넣고, K보다 크면 PriorityQueue의 가장 큰 값과 비교하여 현재 값이 작을 경우 교체를 한다.

static PriorityQueue<Integer>[] dijkstra() {
	PriorityQueue<Vertex> q = new PriorityQueue<>();
	PriorityQueue<Integer>[] kList = new PriorityQueue[N+1];
	
	for (int i = 0; i <= N; i++) {
		kList[i] = new PriorityQueue<>((a, b) -> b-a);
	}
	
	q.add(new Vertex(1, 0));
	kList[1].add(0);
	while(!q.isEmpty()) {
		Vertex vt = q.poll();
		
		for(Vertex v : cities[vt.to]) {
			int cost = vt.weight + v.weight;
			
			if(kList[v.to].size() < K) {
				kList[v.to].add(cost);
				q.add(new Vertex(v.to, cost));
				
			} else if(kList[v.to].peek() > cost){
				kList[v.to].poll();
				kList[v.to].add(cost);
				q.add(new Vertex(v.to, cost));
			}
		}
	}
	
	return kList;
}

 

모든 경로를 구한 후 i번째의 PriorityQueue의 사이즈가 K보다 작으면 K번째 최단경로가 없다는 뜻이므로 -1을 출력하고 아닐 경우 PriorityQueue의 첫 번째 값을 출력한다.

PriorityQueue<Integer>[] D = dijkstra();
for (int i=1; i<=N; i++) {
	PriorityQueue<Integer> d = D[i];
	
	if(d.size() < K)
		sb.append(-1).append('\\n');
	else
		sb.append(d.poll()).append('\\n');
}

---

CODE

package P1854;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * 백준 1854. k번째 최단경로 찾기 - 플래티넘 4
 * @category 데이크스트라
 */
public class Main {
	static class Vertex implements Comparable<Vertex>{
		int to, weight;

		public Vertex(int to, int weight) {
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Vertex o) {
			return this.weight - o.weight;
		}
	}
	
	static int N, M, K;
	static ArrayList<Vertex>[] cities;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken()); // 도시 수
		M = Integer.parseInt(st.nextToken()); // 도로 수
		K = Integer.parseInt(st.nextToken()); // k번째 경로
		
		cities = new ArrayList[N+1];
		for (int i = 0; i <= N; i++) {
			cities[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int from = Integer.parseInt(st.nextToken());;
			int to = Integer.parseInt(st.nextToken());;
			int weight = Integer.parseInt(st.nextToken());;
			
			cities[from].add(new Vertex(to, weight));
		}
		
		StringBuilder sb = new StringBuilder();
		PriorityQueue<Integer>[] D = dijkstra();
		for (int i=1; i<=N; i++) {
			PriorityQueue<Integer> d = D[i];
			
			if(d.size() < K)
				sb.append(-1).append('\\n');
			else
				sb.append(d.poll()).append('\\n');
		}
		
		System.out.println(sb);
	}
	
	static PriorityQueue<Integer>[] dijkstra() {
		PriorityQueue<Vertex> q = new PriorityQueue<>();
		PriorityQueue<Integer>[] kList = new PriorityQueue[N+1];
		
		for (int i = 0; i <= N; i++) {
			kList[i] = new PriorityQueue<>((a, b) -> b-a);
		}
		
		q.add(new Vertex(1, 0));
		kList[1].add(0);
		while(!q.isEmpty()) {
			Vertex vt = q.poll();
			
			for(Vertex v : cities[vt.to]) {
				int cost = vt.weight + v.weight;
				
				if(kList[v.to].size() < K) {
					kList[v.to].add(cost);
					q.add(new Vertex(v.to, cost));
					
				} else if(kList[v.to].peek() > cost){
					kList[v.to].poll();
					kList[v.to].add(cost);
					q.add(new Vertex(v.to, cost));
				}
			}
		}
		
		return kList;
	}
}