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

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

프로그래머스

 

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

우선순위 큐를 통해 intensity가 낮은 값부터 나오게 그래프를 탐색하였습니다. 이때 intensity가 같으면 낮은 봉우리 값이 나와야 하는 조건을 어길 수 있습니다. 그래서 산봉우리라면 answer을 초기화하고 answer의 intensity보다 현재 intensity가 크다면 while문을 종료하도록 하여 문제를 해결하였습니다.

 

import java.util.*;

class Solution {
    private static final int NOT_VISITED = -1;
    private static final int INF = 987654321;
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        int[] answer = new int[]{n,INF};
        boolean[] isFinish = new boolean[n+1];
        for(int summit : summits){
            isFinish[summit] = true;
        }
        List<int[]>[] list = new List[n+1];
        for(int i = 0 ; i <= n ; i++){
            list[i] = new LinkedList<>();
        }
        for(int[] path : paths){
            list[path[0]].add(new int[]{path[1],path[2]});
            list[path[1]].add(new int[]{path[0],path[2]});
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((v1,v2)->{
            if(v1[1] == v2[1]){
                return v1[0] - v2[0];
            }
            return v1[1] - v2[1];
        });
        int[] visited = new int[n+1];
        Arrays.fill(visited,NOT_VISITED);
        for(int gate: gates){
            pq.offer(new int[]{gate,0});
            visited[gate] = 0;
        }
        while(!pq.isEmpty()){
            int[] now = pq.poll();
            // System.out.println(Arrays.toString(now));
            if(isFinish[now[0]]){
                if(answer[1] > now[1]){
                    answer = now;
                }else if(answer[1] == now[1] && answer[0] > now[0]){
                    answer = now;
                }
                continue;
            }
            if(answer[1] < now[1]){
                break;
            }
            for(int[] next : list[now[0]]){
                int temp = Math.max(next[1], now[1]);
                if(visited[next[0]] != NOT_VISITED && visited[next[0]] <= temp ){
                    continue;
                }
                pq.offer(new int[]{next[0],temp});
                visited[next[0]] = temp;
            }
        }
        return answer;
    }
}