PGMS_118669_등산 코스 정하기

다익스트라(Dijkstra) 알고리즘을 사용해서 게이트 ~ 산봉우리까지의 최단 경로를 구하는 문제
조금 다르다면 일반적인 문제들은 총 거리가 최단이 되는 경로를 묻는데 반해 이 문제는 각 노드 사이의 거리가 최소가 되는 경로를 묻는다

왕복 문제이지만 단일 경로를 구한다. 어차피 동일한 경로로 내려오면 되기 때문에 한 정점에서 다른 정점까지의 노드 사이 최단 경로로 구하면 된다

시간복잡도는 O((N+E)logN)인데 N이 5000, E가 200000

주의

게이트 -> 산봉우리가 아니라 산봉우리 -> 게이트로 다익스트라 탐색을 해야한다
왜냐면 조건에 만일 동일한 intensity라면 더 작은 산봉우리 번호를 구한다 가 있기 때문이다
이 조건에 따라 게이트 -> 산봉우리로 구하게 된다면 intensity가 동일한 모든 경로를 구해야 한다

예를 들어, 게이트가 10000개고 모든 노드가 1로 연결되어 있다면? 노드의 종착지가 어떤 산봉우리인지 모르기 때문에 경로를 전부 탐색해야 하는 불상사가 일어나는 것이다...

반대로 산봉우리를 번호가 작은 순으로 정렬한 후에, 산봉우리 -> 게이트로 탐색을 한다면 동일한 intensity는 건너뛰고 더 작은 것만 탐색하면 된다
이미 더 작은 산봉우리의 intensity를 구했기 때문이다

로직

노드 리스트를 만들어서 노드 정보를 넣어준다
contains를 활용하려고 게이트, 산봉우리 정보를 리스트로 만들었다
다익스트라를 돌면서 산봉우리에서 시작해 게이트에 도착할 때까지 dis 배열을 갱신해준다. dis[n]은 노드 n까지 오면서 노드 간 거리가 가장 길었던 것을 넣어준다
산봉우리는 경로에서 한 개만 포함하기 때문에 다른 봉우리를 만나거나, dis[n]을 갱신할 필요가 없거나, 갱신할 값이 intensity보다 작지 않다면 건너뛴다
최소 intensity로 게이트 노드를 만났으면 intensity와 summit을 갱신해준다

삽질

다익스트라의 visited 배열이 헷갈려서 bfs에 노드 넣듯이 썼었다
물론 그러면 안 된다. 저렇게 해서 테스트케이스 2개가 실패가 떴었다. 방문 배열 없애고 값이 갱신될 때마다 pq에 넣어주니까 통과했다
이 부분 외우고는 있는데 원리가 잘 기억이 안 나서 다시 찾아봐야겠다

(세미 삽질) 처음 정답은 반복문으로 summits 배열을 돌리면서 한 노드씩 다익스트라를 돌렸다. 그래도 시간 초과 나진 않았는데, 생각해보니까 정렬 기준만 바꿔주면 모든 산봉우리 노드를 queue에 넣고 한 번에 돌릴 수 있다
원래 정렬은 dis가 작은 순서로 되어있었는데 이걸 2순위로 주고, 1순위 정렬로 산봉우리 노드의 번호가 작은 걸로 줬다. 그리고 pq에 넣어주는 배열에 산봉우리 정보도 포함했다

다시 제출해보니까 확실히 빨라졌다 !

import java.util.*;

class Solution {
    // 내려오든지 말든지 그냥 산봉우리까지 최단 거리 구하면 댄다
    // 다익스트라 쓰는데 거리 말고 intensity 넣으면 될듯?
    static int intensity = 10000001;
    static int summit = 0;

    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        List<int[]>[] nodeList = new ArrayList [n + 1];

        for(int i = 0; i < nodeList.length; i ++) {
            nodeList[i] = new ArrayList<>();
        }

        for(int i = 0; i < paths.length; i ++) {
            int node = paths[i][0];
            int other = paths[i][1];
            int dis = paths[i][2];

            nodeList[node].add(new int [] {other, dis});
            nodeList[other].add(new int [] {node, dis});
        }

        // 게이트 찾기 좋게 list로 바꿈
        List<Integer> gateList = new ArrayList<>();
        for(int i = 0; i < gates.length; i ++) {
            gateList.add(gates[i]);
        }

        // 번호가 낮은 산봉우리부터 탐색
        Arrays.sort(summits);
        
        // 산봉우리 찾기 좋게 list로 바꿈
        List<Integer> summitList = new ArrayList<>();
        for(int i = 0; i < summits.length; i ++) {
            summitList.add(summits[i]);
        }

        // 다익스트라
        dijkstra(nodeList, gateList, summitList, n);

        // 산봉우리 번호랑 intensity 넣기
        int[] answer = {summit, intensity};
        return answer;
    }

    static void dijkstra(List<int[]>[] nodeList, List<Integer> gateList, List<Integer> summitList, int n) {
        Queue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] == o2[2] ? o1[1] - o2[1] : o1[2] - o2[2];
            }
        });

        int[] dis = new int [n + 1];
        Arrays.fill(dis, Integer.MAX_VALUE);

        for (Integer summit : summitList) {
            pq.offer(new int[] {summit, 0, summit});
            dis[summit] = 0;
        }

        while(!pq.isEmpty()) {
            int[] arr = pq.poll();
            int now = arr[0];
            int s = arr[2];

            for(int i = 0; i < nodeList[now].size(); i ++) {
                int[] node = nodeList[now].get(i);
                int next = node[0];
                int nextD = node[1];
                int nowInt = Math.max(dis[now], nextD);

                if(summitList.contains(next) || dis[next] < nowInt || nowInt >= intensity) {
                    continue;
                }

                if(dis[next] > nowInt) {
                    dis[next] = nowInt;
                    pq.offer(new int[] {next, nextD, s});
                }

                if(gateList.contains(next) && dis[next] < intensity) {
                    intensity = dis[next];
                    summit = s;
                }

            }
        }
    }
}