[백준 알고리즘] 1854번 자바(Java) K번째 최단경로 찾기

조건

문제

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

 

입력

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

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

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

출력

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

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

풀이

• 탐색의 과정은 다익스트라 방법을 사용했다
• 문제는 이제 k번째 최단경로를 찾아야 하는 것이고 이를 위해 각 노드에 k크기만큼의 '오름차순' 힙을 생성했다
• 조건은 다음과 같다
  
  • 노드의 힙 크기가 k보다 작다면 거리 cost값을 바로 추가해준다
  • 노드의 힙 크기가 k라면 힙의 peek()과 거리 cost를 비교하고 peek보다 작다면 힙에서 값 하나빼주고 현재 노드의 cost값 추가해준다
  • 거리 cost값이 힙의 peek()보다 크다면 pq에 더이상 추가하지않고 continue해준다
• 이제 다익스트라가 다 끝난후에 각 노드의 힙에 peek()에는 k번째 최단거리값이 남아있거나 아니면 힙의 크기가 k보다 작을 것이다. 이를 통해 출력문을 완성해준다

 

예제 입력 예시

5 10 2
1 2 2
1 3 7
1 4 5
1 5 6
2 4 2
2 3 4
3 4 6
3 5 8
5 2 4
5 4 1

 

예제 출력 예시

-1
10
7
5
14

 

소스코드

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

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

public class Main {
	private static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
	
	private static class Node implements Comparable<Node>{
		int idx;
		int cost;
		public Node(int idx, int cost) {
			this.idx = idx;
			this.cost = cost;
		}
		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.cost, o.cost);
		}
	}
	
	 public static void main(String[] args) throws IOException {
	        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        StringTokenizer st = new StringTokenizer(br.readLine());
	        int n = Integer.parseInt(st.nextToken()); //도시의 수
	        int m = Integer.parseInt(st.nextToken()); //도로 개수
	        int k = Integer.parseInt(st.nextToken()); //k번째 최단거리
	        
	        //k만큼의 값 저장할 힙 저장
	        ArrayList<PriorityQueue<Integer>> kHeap = new ArrayList<>();
	        
	        for(int i = 0; i<n+1; i++) { 
	        	kHeap.add(new PriorityQueue<>(Comparator.reverseOrder())); //내림차순 힙 생성
	        	graph.add(new ArrayList<>());
	        }
	        
	        for(int i = 0; i<m; i++) {
	        	st = new StringTokenizer(br.readLine());
	        	int s = Integer.parseInt(st.nextToken());
	        	int e = Integer.parseInt(st.nextToken());
	        	int c = Integer.parseInt(st.nextToken());
	        	graph.get(s).add(new Node(e,c));
	        }
	        
	        //다익스트라 실행
	        PriorityQueue<Node> pq = new PriorityQueue<>();
	        pq.add(new Node(1,0));
	        while(!pq.isEmpty()) {
	        	Node curNode = pq.poll();
	        	int id = curNode.idx;
	        	int co = curNode.cost;
	        	//조건 kHeap.get[id] 의 크기가 k미만이면 추가가능, 아니면 이제 kHeap.peek()값과 비교해서 빼고 추가해주기
	        	if(kHeap.get(id).size() <k) {	        		
	        		kHeap.get(id).add(co);
	        	}
	        	else if(kHeap.get(id).peek()>co) {
	        		kHeap.get(id).remove();
	        		kHeap.get(id).add(co);
	        	}
	        	else continue;	       
	        		        
	        	//for문
	        	for(Node nextNode : graph.get(id)) {
	        		int nextCompareCost = nextNode.cost + co;
	        			        		
	        		//조건 nextComapreCost가 peek값보다 낮거나 아니면 size아직 덜찼으면 추가
	        		if(kHeap.get(nextNode.idx).size()<k) {
	        			pq.add(new Node(nextNode.idx, nextCompareCost));
	        		}
	        		else if(kHeap.get(nextNode.idx).peek() > nextCompareCost) {
	        			pq.add(new Node(nextNode.idx, nextCompareCost));
	        		}	        		
	        	}	        	
	        }
	        	        	       
	        StringBuilder sb = new StringBuilder();
	        for(int i = 1; i<n+1; i++) { 
	        	if(kHeap.get(i).size()==k) {
	        		sb.append(kHeap.get(i).peek()).append("\n");
	        	}
	        	else {
	        		sb.append(-1).append("\n");
	        	}
	        }	        	        	        	     	   
	        System.out.println(sb);
	    }
}

 

 

 

 

문제 출처

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