[프로그래머스] 등산 코스 정하기

다익스트라를 쓰되, 노드 연결을 할 때 고민을 해야 하는 문제였다.

게이트와 봉우리는 각각 들어오고, 나가고 하나씩만 연결되도록 한 후 다익스트라를 통해 풀이할 수 있었다.

import java.util.*;

class Solution {

    static class Node implements Comparable<Node> {
        int to;
        int v;
        
        public Node() {}
        public Node(int to, int v) {
            this.to = to;
            this.v = v;
        }
        
        public int compareTo(Node o) {
            if(this.v == o.v) return this.to - o.to;
            return this.v - o.v;
        }
    }
    
    static List<Node>[] adj;
    
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        HashSet<Integer> gs = new HashSet<>();
        HashSet<Integer> ss = new HashSet<>();
        
        for(int i : gates) {
            gs.add(i);
        }
        
        for(int i : summits) {
            ss.add(i);
        }
        
        adj = new List[n + 1];
        for(int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < paths.length; i++) {
            int from = paths[i][0];
            int to = paths[i][1];
            int v = paths[i][2];
            
            if(!ss.contains(from) && !gs.contains(to)) {
                adj[from].add(new Node(to, v));
            }
            
            if(!ss.contains(to) && !gs.contains(from)) {
                adj[to].add(new Node(from, v));
            }
        }
        
        return dijkstra(n, gates, summits);
    }
    
    public int[] dijkstra(int n, int[] gates, int[] summits) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        
        int[] intensities = new int[n + 1];
        Arrays.fill(intensities, Integer.MAX_VALUE);
        
        for(int i : gates) {
            pq.add(new Node(i, 0));
            intensities[i] = 0;
        }
        
        while(!pq.isEmpty()) {
            Node curr = pq.poll();
            
            if(curr.v > intensities[curr.to]) continue;
            
            for(Node next : adj[curr.to]) {
                int nextIntensity = Math.max(next.v, intensities[curr.to]);
                
                if(intensities[next.to] > nextIntensity) {
                    intensities[next.to] = nextIntensity;
                    pq.add(new Node(next.to, nextIntensity));
                }
            }
        }
        
        int minIntensity = Integer.MAX_VALUE;
        int minSummit  = -1;
        
        for(int i : summits) {
            if(minIntensity >= intensities[i]) {
                if(minIntensity > intensities[i]) {
                    minSummit = i;
                }
                minSummit = Math.min(minSummit, i);
                minIntensity = intensities[i];
            }
        }
        
        return new int[] {minSummit, minIntensity};
    }
    
}