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

🔺 문제

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

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    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());   // 몇 번째 최단 경로인지
        
        // 정렬 기준 설정 (내림차순)
        Comparator<Integer> cp = new Comparator<>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 < o2 ? 1 : -1;
            }
        };
        
        // 최단 거리 큐 배열 초기화
        PriorityQueue<Integer>[] distQ = new PriorityQueue[N + 1];
        for(int i = 0 ; i <= N ; i++) {
            distQ[i] = new PriorityQueue<Integer>(K, cp);
        }
        
        // 인접 행렬에 그래프 데이터 저장
        int[][] W = new int[1001][1001];
        while(M --> 0) {
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            
            W[a][b] = c;
        }
        
        
        // 다익스트라 수행
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0));
        distQ[1].add(0);
        
        while(!pq.isEmpty()) {
            Node u = pq.poll();
            
            for(int adjNode = 1 ; adjNode <= N ; adjNode++) {
                // 연결된 모든 노드로 검색
                if(W[u.node][adjNode] != 0) {
                    
                    // 저장된 경로가 K가 안 되면 그냥 추가
                    if(distQ[adjNode].size() < K) {
                        distQ[adjNode].add( u.cost + W[u.node][adjNode] );
                        pq.add(new Node(adjNode, u.cost + W[u.node][adjNode]));
                    }
                    
                    // 저장된 경로가 K개이고, 현재 가장 큰 값보다 작을 때만 추가
                    else if(distQ[adjNode].peek() > u.cost + W[u.node][adjNode]) {
                        distQ[adjNode].poll();                                  // 기존 큐에서 Max값(=마지막값) 먼저 삭제
                        distQ[adjNode].add( u.cost + W[u.node][adjNode] );      // 신규값 업데이트
                        pq.add(new Node(adjNode, u.cost + W[u.node][adjNode])); // 큐에 선택 노드 추가
                    }
                }
            }
        }
        
        
        // K번째 경로 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 1 ; i <= N ; i++) {
            if(distQ[i].size() == K) sb.append(distQ[i].peek()).append("\n");
            else                     sb.append(-1).append("\n");
        }
        System.out.println(sb);
    }
}
 
// 노드 클래스 작성
class Node implements Comparable<Node>{
    int node;
    int cost;
    
    Node(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Node n) {
        return this.cost - n.cost;
    }
}

✅ 해결 아이디어
✔ 다익스트라
- 최단 경로 배열, 각각 하나의 크기가 K인 우선순위 큐 배열로 선언

 

💥 유의사항

⇨ 우선선위 큐 배열 선언 방법

PrirorityQueue<Integer>[] distQ = new PriorityQueue[N + 1];

  → 우선순위 큐의 크기 & 정렬 기준 위한 코드 작성 필요

 

 

⇨ 최단 거리 배열 채우기 규칙

1) 현재 노드에 저장된 경로 수 < K 일 때, 신규 경로 추가
2) 경로 == K일 때, 현재 경로 중 최대 경로 > 신규 경로일 때 업데이트
3) 사용한 노드는 방문 배열에 확인해 두고, 재사용하지 않는 부분은 삭제.

•  

 

---

🔺 다른 풀이들

- 가장 깔끔 & 인접 리스트 , 향상형 for문 사용하심

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

 

- 인접 행렬/리스트 사용을 안 하심...

[백준 1854 : JAVA] K번째 최단경로 찾기 / 다익스트라

 

 

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

 

 

- 도시별 최단거리 경로 배열 정렬할 때, Comparator 사용 안 하고
 costList[n] = newPriorityQueue<>(Collections.reverseOrder());로 한 줄 처리

백준 1854 K번째 최단경로

 

[자바] 백준 1854 - K번째 최단경로 찾기

 

 

- 과정 설명이 복습용으로 굿

백준 1854번 - K번째 최단경로 찾기

---

💬 느낀 점

이야....

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 우선순위 큐 정렬 기준 만들기

[자바/java] 우선순위 큐 정렬하기 priorityQueue sort

 

[JAVA] 우선순위 큐 (Priority Queue), 정렬 전략 설정법