[BOJ] 백준 1854번 K번째 최단경로 찾기 (Java)

#1854 K번째 최단경로 찾기

난이도 : 플레 5

유형 : 그래프 / 다익스트라

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을 출력한다. 최단경로에 같은 정점이 여러 번 포함되어도 된다.

 

문제 풀이  

1번 도시에서 i번 도시로 가는 k번째 최단경로를 구하는 문제이다. 한 정점에 다른 모든 정점의 최단거리를 구하는 것이기 때문에 다익스트라 알고리즘을 해당 풀이의 베이스로 사용할 것이다. 

 

📚 조건

• 도시의 개수 n (1 ≤ n ≤ 1000)
• 도로의 개수 m (0 ≤ m ≤ 2000000)
• k번째 최단경로 (1 ≤ k ≤ 100) 
• 최단경로에 같은 정점 포함 (→ 방문체크 x)
• i → i 1번째 최단경로는 0

 

해당 그래프의 2번째 최단경로를 구해보자.

예제 그래프

도시(i)	1번째 최단경로 (1 →i)	2번째 최단경로 (1 →i)
1	0	-1 (존재 x)
2	2 (1→2)	10 (1→5→2)
3	6 (1→2→3)	7 (1→3)
4	4 (1→2→4)	5 (1→4)
5	6 (1→5)	14 (1→2→3→5)

 

그냥 다익스트라 알고리즘을 사용하면 1번째 최단경로[0,2,6,4,6]밖에 구하지 못하므로 다익스트라 로직에 무언가를 첨가해줘야한다.

1) 각 도시 재방문 가능

다익스트라는 우선순위 큐를 사용하여 시작 정점(1)과 연결되어있는 도로 중 작은 것부터 탐색을 시작해준다. 원래의 로직이라면 방문했던 도시들은 재방문을 해주지 않아야하지만 k번째 경로를 찾을때까지 탐색해줘야하므로 방문여부를 체크해주지 않을 것이다.

// if(check[to]) continue;
// else check[to] = true;

 

2) 촤대 힙 배열에 최단경로 저장 및 갱신

기존 다익스트라 로직은 경로를 1차 배열 dp에 저장하여 최단경로를 갱신해줬는데 k번째의 최단경로를 저장하기위해서는 각 dp에 사이즈가 최대 k인 최대 힙을 입혀 최단경로를 계속해서 갱신해줄 것이다. 

Queue<Integer>[] dis; = new PriorityQueue[n+1];
for(int i=1; i<n+1; i++) {
	dis[i] = new PriorityQueue<>(Collections.reverseOrder());// 최대 힙 (내림차순)  
}

 

최대 힙(Max Heap)은 루트 노드로 올라갈 수록 값이 커지는 구조를 가진다. 그러므로 현재 k개 중 가장 큰 값인 루트노드 peek()이 새로운 경로보다 클 경우 해당 루트노드를 삭제하고 새로운 경로 값을 넣어준다. 이렇게 최소의 값을 갖는 k개의 집합을 구해주면 된다.

//k개 최단경로 저장  
if(dis[nxt.t].size()<k) {
	dis[nxt.t].add((weight+nxt.w));
	q.add(new City(nxt.t, weight+nxt.w));
}
// dis[nxt.t].size() == k이고,
// k번째 최단경로(dis[nxt.to].peek())보다 현재 경로(weight+nxt.w)가 더 작으면 최단경로 갱신
else if(dis[nxt.t].peek() > weight+nxt.w) { 
	dis[nxt.t].poll();
	dis[nxt.t].add(weight +nxt.w);
	q.add(new City(nxt.t, weight + nxt.w));
}

 

풀이 코드 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int n,m,k;
	static List<City>[] list;
	static Queue<Integer>[] dis;
	static class City implements Comparable<City>{
		int t;
		int w;
		
		public City(int t, int w) {
			this.t = t;
			this.w = w;
		}

		@Override
		public int compareTo(City o) {
			return this.w - o.w;
		}
	}
	public static void main(String[] args) throws IOException{
		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());
		
		dis = new PriorityQueue[n+1];
		list = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			dis[i] = new PriorityQueue<>(Collections.reverseOrder());// 최대 힙 (내림차순)  
			list[i] = new ArrayList<>();
		}
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int f = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			list[f].add(new City(t,w));
		}
		
		solve(1);
		 for (int i = 1; i < n+1; ++i){
			if (dis[i].size() == k) System.out.println(dis[i].peek());
			else System.out.println(-1);
		}
	}
	
	static void solve(int start) {
		Queue<City> q = new PriorityQueue<>();
		q.add(new City(start,0));
		dis[start].add(0); //i → i 1번째 최단경로는 0

		while(!q.isEmpty()) {
			City pos= q.poll();
			int to = pos.t;
			int weight = pos.w;
			
			for(City nxt : list[to]) {
				//k개 최단경로 저장  
				if(dis[nxt.t].size()<k) {
					dis[nxt.t].add((weight+nxt.w));
					
					q.add(new City(nxt.t, weight+nxt.w));
					
				}
				// dis[nxt.t].size() == k이고,
				// k번째 최단경로(dis[nxt.to].peek())보다 현재 경로(weight+nxt.w)가 더 작으면 최단경로 갱신
				else if(dis[nxt.t].peek() > weight+nxt.w) { 
					dis[nxt.t].poll();
					dis[nxt.t].add(weight +nxt.w);
					
					q.add(new City(nxt.t, weight + nxt.w));
				}
			}
		}
	}
}