프로그래머스-등산 코스 정하기(다익스트라)

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

프로그래머스

 

다익스트라는 감을 잡은 것 같다. '완화'를 사용하는 경우에서 문제의 난이도가 갈린다.

이 문제 또한 완화를 어떻게 사용할 지에 대해 고민하면 쉽게 풀리는 문제였다.

import java.util.*;

class Solution {
    List<int[]>[] graph;
    int[] values;
    Set<Integer> summitSet = new HashSet<>();

    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        initialize(n, paths, summits);
        int[] max;
        
        dijkstra(gates);

        int[] answer = new int[]{0, Integer.MAX_VALUE};
        for (int i = 0; i < summits.length; i++) {
            if (answer[1] > values[summits[i]]) {
                answer = new int[]{summits[i], values[summits[i]]};
            }else if(answer[1] == values[summits[i]] && answer[0] > summits[i]){
                answer = new int[]{summits[i], values[summits[i]]};
            }
        }
        return answer;
    }

    private void dijkstra(int[] starts) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
        for(int s : starts){
            values[s] = 0;
            queue.add(new int[]{s, 0});
        }
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int cur_k = cur[0];
            int cut_v = cur[1];
            for(int[] next : graph[cur_k]){
                int next_k = next[0];
                int next_v = next[1];
                //완화 : 현 경로까지 가장 큰 시간보다 더 작은 시간이 있다면, 굳이 가지 않는다.
                // => 효율적이라면 진행한다고 생각하자.
                if(Math.max(values[cur_k], next_v) >= values[next_k])continue;
                if(isSummit(next_k)){
                    values[next_k] = Math.max(values[cur_k], next_v);
                    continue;
                }
                //완화 : 현 경로까지 가장 효율적일때, 값을 업뎃해준다.
                values[next_k] = Math.max(values[cur_k], next_v);
                queue.add(new int[]{next_k, next_v});
            }
        }
    }

    private boolean isSummit(int node) {
        return summitSet.contains(node);
    }

    public void initialize(int n, int[][] paths, int[] summits) {
        graph = new ArrayList[n + 1];
        values = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
            values[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < paths.length; i++) {
            int start = paths[i][0];
            int end = paths[i][1];
            int value = paths[i][2];
            graph[start].add(new int[]{end, value});
            graph[end].add(new int[]{start, value});
        }

        for (int i = 0; i < summits.length; i++) {
            summitSet.add(summits[i]);
        }
    }
}