[Programmers] Level 3 :: 등산 코스 정하기 Java 풀이

프로그래머스

약간의 테크닉이 필요한 다익스트라 응용 문제이다.
출발점 노드들이 주어지고, 산봉우리 노드들이 주어진다. 출발지 노드를 start라 하고, 산봉우리 노드를 end라고 하겠다.

우리가 구하고 싶은 값은 start -> end -> start로 탐색을 진행할때 지나온 간선의 가중치 최솟값이다. 여기서 약간만 생각하면 start -> end만 구해도 된다는 것을 눈치챌 수 있다. 굳이 end -> start를 탐색할 필요가 없기 때문이다. 그냥 start -> end에 도달하는 경로를 찾았다면 그 길을 따라서 그대로 end -> start로 내려오면 된다.

따라서 문제를 start -> end로 이동할때, 지나가는 간선의 최댓값 중 최솟값을 구하면 된다 라고 변형할 수 있다.

이제 start -> end로 탐색을 시작해야 하는데, 효율적인 그래프 탐색을 위해 다익스트라를 떠올려볼 수 있다. 보통 다익스트라는 최소 경로를 기준으로 돌리게 되는데, 모든 경로의 길이를 더하는 것이 아니라, 지나온 간선 가중치 최댓값을 기준으로 다익스트라를 돌리면 문제에 그대로 적용할 수 있다.

자, 그럼 각 노드를 기준으로 위의 로직을 구현하면 될것이다.. 라기엔 시간복잡도가 MlogN * N이기 때문에 터져버린다. 여기서 테크닉이 등장하는데, 모든 시작점 노드를 한번에 pq에 넣고 다익스트라를 돌리는 테크닉을 쓰자. 그러면 O(MlogN)에 풀린다. 

실제 코테에서 풀었던 문제긴 하지만, 못풀어도 전혀 합격에 지장이 없는 어려운 문제인 것 같다.

import java.util.*;

class Solution {
    
    private List<Node>[] graphs = new ArrayList[50010];


    private int[] visited = new int[50010];
    private boolean[] isSummits = new boolean[50010];
    private PriorityQueue<Curr> pq = new PriorityQueue<Curr>();
    
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        for (int i = 0; i < graphs.length; i++) {
            graphs[i] = new ArrayList<Node>();
        }
        for (int i=0; i<=n; i++) {
            visited[i] = 1000000000;
        }
        for (int i=0; i<summits.length; i++) {
            isSummits[summits[i]] = true;
        }
        for (int[] path: paths) {
            int x = path[0];
            int y = path[1];
            int z = path[2];
            graphs[x].add(new Node(y, z));
            graphs[y].add(new Node(x, z));
        }
        for(int gate: gates) {
            visited[gate] = 0;
            pq.add(new Curr(gate, 0));
        }
        
        while (pq.size() != 0) {
            Curr curr = pq.poll();
            if (visited[curr.node] < curr.dist) continue;
            for (Node next: graphs[curr.node]) {
                if (visited[next.x] <= Math.max(curr.dist, next.y)) continue;
                visited[next.x] = Math.max(curr.dist, next.y);
                if (isSummits[next.x]) continue;
                pq.add(new Curr(next.x, visited[next.x]));
            }
        }
        
        int mini = 1000000000;
        int node = 0;
        for (int summit: summits) {
            if (visited[summit] < mini) {
                mini = visited[summit];
                node = summit;
            } else if (visited[summit] == mini && summit < node) {
                mini = visited[summit];
                node = summit;              
            }
        }
        int[] answer = {node, mini};
        return answer;
    }
    
    static class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static class Curr implements Comparable<Curr> {
        int node;
        int dist;
        
        public Curr(int node, int dist) {
            this.node = node;
            this.dist = dist;
        }
        
        @Override
        public int compareTo(Curr a) {
            return this.dist - a.dist;
        }
        
    }
}