접근
Dijkstra 알고리즘을 써야하는 것을 미리 알고 접근하였음.
일반적인 다익스트라 알고리즘은 항상 탐색한 경로에서 갈 수 있는 최단 거리를 방문하고, 최단거리를 만들어 가면서 한번 방문한 노드는 재방문하지 않음.
하지만 여기서 요구하는 최단거리는 거리에 따른 k번째 경로를 요구한다.
그래서 기본적인 다익스트라에 요구되는 "재방문하지 않는다." 라는 조건을 없애고, 같은 노드에 여러 번 들어가면서 해당 노드로의 k번째 경로를 만들어주는 것을 목표로 하였음.
기본 조건
- 일반 Dijkstra
- 처음 방문한 노드라면(이미 방문한 노드가 아니라면)
- 또는, 재차 방문 했을 때, 지나온 거리가 현재 노드로의 최단 거리보다 작을 때
- k번째 최단거리를 구하기 위한 조건
- 현재 구한 거리의 개수가 k 보다 작을 때, 해당 노드로의 거리 리스트에 추가함
- k보다 크거나 같다면, k번째에 위치한 최단거리보다 작다면 해당 위치에 새로운 최단 거리를 삽입한다.
1) 여기서 m은 최대 200만개 이고, 구할 수 있는 최대 최단거리의 개수 k는 100개가 최대이므로, 최단거리를 나올때마다 다익스트라 순환큐에 집어 넣으면 당연히 시간초과가 날 것으로 생각하였다.
2) 그래서 노드 i의 k번째 최단거리 리스트에 삽입하기 위해서 조건을 충족하지 않거나, 이미 k번째가 완성되어서, 계속해서 k번째 최단거리보다 더 큰 거리의 값이 나온다면 큐에 더 이상 들어가지 않도록 제한을 걸 수 있도록 구현하기로 하였다.
3) 또한 값을 삽입하기 위한 k번쨰 위치 등을 찾기 위해서 200만이나 되는 간선에 대한 부담을 줄이기 위해 이진탐색을 통해서 삽입 위치를 빠르게 찾을 수 있었다.
코드
import java.util.*;
import java.io.*;
public class BackJoonMemo {
// 1) 노드 리스트를 구하기 위한 커스텀 클래스
static class Node implements Comparable<Node>{
int vertex;
int time;
// 1-1) k번째 최단 경로를 우선순위 큐로 판별하기 위한 변수
int stackedTime;
public int compareTo(Node n){
return this.stackedTime - n.stackedTime;
}
Node(int n, int t, int st){
this.vertex = n;
this.time = t;
this.stackedTime = st;
}
}
static ArrayList<Node>[] edges; // i번째 노드에 연결된 간선 목록
static ArrayList<Integer>[] distance; // i번째 노드로의 최단 경로 목록
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// n = 노드의 수, m = 간선의 수, k = 구하고자 하는 최단 거리의 번째
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());;
int k = Integer.parseInt(st.nextToken());;
edges = new ArrayList[n+1];
distance = new ArrayList[n+1];
for(int i = 1; i<=n; i++){
edges[i] = new ArrayList<>();
distance[i] = new ArrayList<>();
}
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());
// 처음에는 최단 경로 스택을 간선의 가중치부터 시작
edges[a].add(new Node(b, c, c));
}
recursiveDijkstra(1, k);
for(int i = 1; i<=n; i++){
if(distance[i].size() < k){
System.out.println(-1);
}else{
System.out.println(distance[i].get(k-1));
}
}
for(int i = 1 ;i <=n ; i++){
}
}
static void recursiveDijkstra(int start, int k){
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.add(new Node(start, 0, 0));
distance[start].add(0);
// 2) 일반적인 다익스트라 알고리즘을 따르되, 재방문이 가능하다.
while(!queue.isEmpty()){
Node currNode = queue.poll();
ArrayList<Node> edge = edges[currNode.vertex];
for(Node node : edge){
// 2-1) 현재 최단 거리에서 다음 노드까지 걸리는 새로운 최단거리
int newDist = currNode.stackedTime + node.time;
// 2-2) 만일 아직 해당 노드까지 최단거리 개수가 k가 미만이거나,
// k번째 보다 크거나 같다면, k번째에 위치한 최단거리가 현재 구한
// 새로운 최단거리와 비교해서 더 작을 때 새로운 k번째 최단거리로 판별한다.
int nextNodeDistSize = distance[node.vertex].size();
if(nextNodeDistSize < k || distance[node.vertex].get(nextNodeDistSize - 1) > newDist){
// 3) 또한, k의 크기와 간선이 최대 100과 200만개이기 때문에,
// 간선의 개수에 따른 모든 경우의 수를 큐에 집어넣으면
// 너무 많고 탐색하는데도 오래걸리기 때문에 이진탐색을 통해서 삽입할 위치를 찾음.
binarySearchInsert(node.vertex, newDist);
queue.add(new Node(node.vertex, node.time, newDist));
}
}
}
}
static void binarySearchInsert(int vertex, int value){
ArrayList<Integer> currDistances = distance[vertex];
int left = 0;
int right = currDistances.size() - 1;
// 찾으려는 위치의 값보다 현재 넣으려는 최단경로의 길이가 더 작다면, 해당위치의 오른쪽에 삽입
// "" 더 크다면, 해당 위치의 왼쪽에 삽입
// "" 크기가 같은 최단경로라면, 해당위치에 그대로 삽입.
int mid;
while(left <= right){
mid = left + (right - left) / 2;
if(currDistances.get(mid) < value){
left = mid + 1;
}else if (currDistances.get(mid) > value){
right = mid - 1;
}else{
left = mid;
break;
}
}
currDistances.add(left, value);
}
}
실수한 부분
k번째 최단거리를 집어넣는 조건에서 아래 처럼, 현재 노드로의 최단거리에 마지막 값이랑 비교해서 시간초과가 났다.
nextNodeDistSize - 1 -> k - 1로 변경하였음.
처음에 생각했는데 급하게 한다고 해당 부분에서 실수했고, 바로 고쳐서 정답으로 하였다.
if(nextNodeDistSize < k || distance[node.vertex].get(nextNodeDistSize - 1) > newDist){
binarySearchInsert(node.vertex, newDist);
queue.add(new Node(node.vertex, node.time, newDist));
}결과
