[2022 KAKAO TECH INTERNSHIP] 등산코스 정하기

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

프로그래머스

• 출입구를 A,  산봉우리를 B라고 할 때, A -> ... -> B -> ... -> A의 경로로 이동한다. 그리고 가장 작은 intensity를 구하면 된다. 
• 이때 출입구 A -> 산봉우리 B로 이동할 때의 최소 intensity만 구하면 된다.
  • B -> A에서의 최소 intensity는 A -> B로 올라온 경로로 똑같이 내려가면 되기 때문이다.
  • 이렇게 생각하면 별도의 중복 처리 없이 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 하는 규칙을 지킬 수 있다.
• 그리고 최소 intensity를 구해야 하는데 이때 사용되는 배열은 intensity[]이고 intensity[i]는 출입구에서 i까지 오를 때 intensity들 중 최댓값이다. 그리고 각각의 출입구에서 각각의 산봉우리까지 오르는데 intensity[B]의 최솟값을 구하면 된다. 이때 다익스트라로 다음과 같은 경우에 intensity 배열 값을 갱신해주면 된다.
  • if(intensity[to] > max(intensity[from], from~to로의 intensity)) 
    intensity[to] = max(intensity[from], from~to로의 intensity)

• 그리고 처음에는 출입구마다 다익스트라를 진행해서 시작점 1에서 산봉우리들까지의 거리, 시작점 2에서 산봉우리들까지의 거리, .... 를 모두 계산했다. 그랬더니 시간 초과가 났다. 알고보니 그냥 시작점을 모두 큐에 넣어서 한 번만 다익스트라를 진행하면 된다. 어차피 각 산봉우리까지 걸리는 intensity의 최솟값만 구하면 되기 때문에 시작점이 어디였든지 간에 구분해줄 필요는 없는 거 같다.
• 마지막으로 주의할 점은 intensity가 최소가 되는 등산코스가 여러 개라면 그 중 산봉우리 번호가 가장 낮은 등산코스를 선택해야 한다는 점이다. 따라서 산봉우리 번호가 낮은 순으로 정렬해서 값을 도출해야 한다. 이 부분을 못 봐서 계속 틀렸는데.. 문제를 꼼꼼하게 잘 읽자!!!!!!!!

import java.util.*;

class Solution {

    int n;
    int[][] paths;
    int[] gates;
    int[] summits;
    List<List<Node>> list = new ArrayList<>();
    int[] dist;

    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        this.n = n;
        this.paths = paths;
        this.gates = gates;
        this.summits = summits;
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }

        // 출입구 -> 정상으로의 최소 비용만 구하면 된다.
        for (int[] path : paths) {
            int v1 = path[0];
            int v2 = path[1];
            int intensity = path[2];
            // 단방향
            if (isGate(v1) || isSummit(v2)) {
                list.get(v1).add(new Node(v2, intensity));
            } else if (isSummit(v1) || isGate(v2)) {
                list.get(v2).add(new Node(v1, intensity));
            }
            // 양방향
            else {
                list.get(v1).add(new Node(v2, intensity));
                list.get(v2).add(new Node(v1, intensity));
            }
        }

        dijkstra(); // 다익스트라

        Arrays.sort(summits); // 산봉우리 번호가 낮은 순서대로 정렬
        int minIntensity = Integer.MAX_VALUE;
        int summitNum = 0;
        for (int summit : summits) {
            if (dist[summit] < minIntensity) {
                minIntensity = dist[summit];
                summitNum = summit;
            }
        }

        return new int[]{summitNum, minIntensity};
    }

    private void dijkstra() {
        PriorityQueue<Node> que = new PriorityQueue<>();
        dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        boolean[] visited = new boolean[n + 1];

        // 시작점
        for (int gate : gates) {
            dist[gate] = 0;
            que.add(new Node(gate, 0));
        }

        while (!que.isEmpty()) {
            Node now = que.poll();

            if (visited[now.end]) continue;
            visited[now.end] = true;

            for (Node node : list.get(now.end)) {
                if (dist[node.end] > Math.max(dist[now.end], node.intensity)) {
                    dist[node.end] = Math.max(dist[now.end], node.intensity);
                    que.add(new Node(node.end, dist[node.end]));
                }
            }
        }
    }

    private boolean isSummit(int v) {
        for (int summit : summits) {
            if (summit == v) {
                return true;
            }
        }
        return false;
    }

    private boolean isGate(int v) {
        for (int gate : gates) {
            if (gate == v) {
                return true;
            }
        }
        return false;
    }

    class Node implements Comparable<Node> {
        int end, intensity;

        public Node(int end, int intensity) {
            this.end = end;
            this.intensity = intensity;
        }

        @Override
        public int compareTo(Node o) {
            return intensity - o.intensity;
        }
    }
}