[백준] 1854 : K번째 최단경로 찾기 - JAVA

🙋🏻‍♀️다익스트라 알고리즘 사용!

다른건 괜찮은데, k번째 최단경로를 어떻게 구할지가 큰 의문이었다.
도저히 생각나지않아 해설을 보고 공부했다.

K번째 최단경로 해결 방법

• 최단 경로를 표현하는 배열을 우선순위 큐 배열(크키K)로 변경한다.

여기서 나는 우선순위 큐 배열이라는 것을 처음 접했다.
PriorityQueue<Integer>[] distQueue = new PriorityQueue[n+1]; 이렇게 선언해서 사용할 수 있다.
이에 관해 우선순위 큐의 크기와 정렬 기준을 위해서는 따로 코드를 작성해야한다.

Troubleshooting

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
public static int[][] list;
public static PriorityQueue<Integer>[] distQueue;
public static int k,n;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n =  Integer.parseInt(st.nextToken());
		int m =  Integer.parseInt(st.nextToken());
		k =  Integer.parseInt(st.nextToken());
		distQueue = new PriorityQueue[n+1];
		Comparator<Integer> cp = new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1<o2 ? 1 : -1;
			}
		};
		for(int i=1; i<n+1; i++) {
			distQueue[i] = new PriorityQueue<Integer>(k,cp);
		}
		list = new int[n+1][n+1];
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			list[a][b] = c;
		}
		dijkstra(list, distQueue);
		for(int i=1; i<n+1; i++) {
			if(distQueue[i].size() == k) bw.write(distQueue[i].peek() + "\n");
			else bw.write("-1" + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
	
	public static void dijkstra(int[][] list,PriorityQueue<Integer>[] distQueue) {
		PriorityQueue<kNode> pq = new PriorityQueue<>();
		pq.offer(new kNode(1,0));
		while(!pq.isEmpty()) {
			kNode now = pq.poll();
			for(int i=1; i<n+1; i++) {
				if(list[now.node][i] != 0) {
					if(distQueue[i].size() < k) {
						distQueue[i].offer(now.time + list[now.node][i]);
						pq.offer(new kNode(i, now.time + list[now.node][i]));
					} else {
						if(distQueue[i].peek() > now.time + list[now.node][i]) {
							distQueue[i].poll();
							distQueue[i].add(now.time + list[now.node][i]);
							pq.add(new kNode(i, now.time + list[now.node][i]));
						}
					}
				}
			}
		}
	}
}
class kNode implements Comparable<kNode>{
	int node;
	int time;
	kNode(int targetNode, int time) {
		this.node = targetNode;
		this.time = time;
	}
	@Override
	public int compareTo(kNode n) {
		if(this.time> n.time) return 1;
		else return -1;
	}	
}

문제

예제의 출력은 맞았는데, 틀렸습니다를 받았다.

원인

처음에 1로 시작할 때, 이 거리 0을 distQueue에 넣어주지 않아서 생긴 문제였다.

해결

dijkstra 메소드에서 pq.offer(new kNode(1,0));할 때, distQueue[1].add(0); 코드를 추가해서 우선순위큐배열에 거리 0값을 추가했다.

제출 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
public static int[][] list;
public static PriorityQueue<Integer>[] distQueue;
public static int k,n;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n =  Integer.parseInt(st.nextToken());
		int m =  Integer.parseInt(st.nextToken());
		k =  Integer.parseInt(st.nextToken());
		distQueue = new PriorityQueue[n+1];
		Comparator<Integer> cp = new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1<o2 ? 1 : -1;
			}
		};
		for(int i=1; i<n+1; i++) {
			distQueue[i] = new PriorityQueue<Integer>(k,cp);
		}
		list = new int[n+1][n+1];
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			list[a][b] = c;
		}
		dijkstra(list, distQueue);
		for(int i=1; i<n+1; i++) {
			if(distQueue[i].size() == k) bw.write(distQueue[i].peek() + "\n");
			else bw.write("-1" + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
	public static void dijkstra(int[][] list,PriorityQueue<Integer>[] distQueue) {
		PriorityQueue<kNode> pq = new PriorityQueue<>();
		pq.offer(new kNode(1,0));
		distQueue[1].add(0);
		while(!pq.isEmpty()) {
			kNode now = pq.poll();
			for(int i=1; i<n+1; i++) {
				if(list[now.node][i] != 0) {
					if(distQueue[i].size() < k) {
						distQueue[i].offer(now.time + list[now.node][i]);
						pq.offer(new kNode(i, now.time + list[now.node][i]));
					} else {
						if(distQueue[i].peek() > now.time + list[now.node][i]) {
							distQueue[i].poll();
							distQueue[i].add(now.time + list[now.node][i]);
							pq.add(new kNode(i, now.time + list[now.node][i]));
						}
					}
				}
			}
		}
	}
}
class kNode implements Comparable<kNode>{
	int node;
	int time;
	kNode(int targetNode, int time) {
		this.node = targetNode;
		this.time = time;
	}
	@Override
	public int compareTo(kNode n) {
		if(this.time> n.time) return 1;
		else return -1;
	}	
}

공부한 사항

• 우선순위 큐 배열
  <선언 및 초기화>
  PriorityQueue<Integer>[] distQueue = new PriorityQueue[n+1];

for(int i=1; i<n+1; i++) {
	distQueue[i] = new PriorityQueue<Integer>(k,cp);
}

생성자 PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
:기본크기와 특정한 순서를 가진 우선순위 큐를 생성한다.