프로그래머스 등산코스 정하기 (JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

 

저는 우선순위 큐를 통해 문제를 해결하였습니다.

우선순위 큐를 통해 intensity가 작은 것 부터 나오도록 하였습니다.

intensity가 낮은 것 부터 이동을 진행하면서 summit인 것을 찾습니다.

summit이 발견되면 minValue와 minSummit을 초기화하고, 만약 intnesity가 minValue보다 크다면 while문을 빠져나오도록 하였습니다.

 

import java.util.*;
class Solution {
    private static final int INF = 987654321;
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        int[] answer = {};
        List<int[]>[] map = new List[n+1];
        for(int i = 0 ; i <= n ; i++){
            map[i] = new LinkedList<>();
        }
        for(int[] path : paths){
            map[path[0]].add(new int[] {path[1],path[2]});
            map[path[1]].add(new int[] {path[0],path[2]});
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
        Set<Integer> stop = new HashSet<>();
        Map<Integer,Integer> visited = new HashMap<>();
        for(int gate : gates){
            pq.offer(new int[] {gate,0});
            visited.put(gate,0);
        }
        for(int summit : summits){
            stop.add(summit);
            
        }
        int minValue = INF;
        int minSummit = INF;
        while(!pq.isEmpty()){
            int[] now = pq.poll();
            if(minValue < now[1]){
                break;
            }
            if(stop.contains(now[0])){
                minValue = now[1];
                minSummit = Math.min(minSummit, now[0]);
                answer = new int[] {minSummit, minValue};
                continue;
            }
            for(int[] path : map[now[0]]){
                int[] next = new int[]{path[0],Math.max(now[1],path[1])};
                if(visited.getOrDefault(next[0],INF) > next[1]){
                    visited.put(next[0],next[1]);
                    pq.offer(next);
                }
            }
        }
        return answer;
    }
}