[프로그래머스 - 자바] 등산 코스 정하기

문제 링크

• 등산코스 정하기

풀이

• 저번 카카오 인턴십 코테 당시에는 시간초과와 런타임 에러가 발생했다. 근데 이번에 다시 풀어보니 무난하게 풀 수 있었다!
• 설명에서는 출발지 -> 산봉우리 -> 출발지로 설명을 했지만, 출발지 -> 산봉우리까지의 intensity만 구하면 된다. 이를 통해 최단거리 대신 intensity를 사용한 다익스트라 문제임을 알았다.
• 출발지와 산봉우리는 한번씩만 거칠 수 있으므로, 현재 노드가 산봉우리나 출발지라면 등산을 종료시켰다.
• summits가 정렬되어 있지 않음에 주의하자.

코드

import java.util.*;

class Solution {
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        ArrayList<ArrayList<Node>> graph = createGraph(n, paths);
        HashMap<Integer, Boolean> summitMap = createSummitMap(summits);
        HashMap<Integer, Boolean> gateMap = createGateMap(summits);
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Arrays.sort(summits);

        int[] intensities = new int[n + 1];
        Arrays.fill(intensities, Integer.MAX_VALUE);

        for (int gate : gates) {
            pq.offer(new Node(gate, 0));
            intensities[gate] = 0;
        }

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

            if (gateMap.containsKey(now.index) || summitMap.containsKey(now.index)) {
                continue;
            }

            if (intensities[now.index] < now.intensity) {
                continue;
            }

            for (Node next : graph.get(now.index)) {
                int intensity =
                        (next.intensity == Integer.MAX_VALUE) ? now.intensity : Math.max(next.intensity, now.intensity);
                if (intensities[next.index] > intensity) {
                    intensities[next.index] = intensity;
                    pq.offer(new Node(next.index, intensity));
                }
            }
        }

        int index = -1;
        int minIntensity = Integer.MAX_VALUE;
        for (int summit : summits) {
            if (intensities[summit] < minIntensity) {
                minIntensity = intensities[summit];
                index = summit;
            }
        }
        return new int[]{index, minIntensity};
    }

    private static HashMap<Integer, Boolean> createGateMap(int[] gates) {
        HashMap<Integer, Boolean> gateMap = new HashMap<>();
        for (int gate : gates) {
            gateMap.put(gate, true);
        }
        return gateMap;
    }

    private static HashMap<Integer, Boolean> createSummitMap(int[] summits) {
        HashMap<Integer, Boolean> summitMap = new HashMap<>();
        for (int summit : summits) {
            summitMap.put(summit, true);
        }
        return summitMap;
    }

    private ArrayList<ArrayList<Node>> createGraph(int n, int[][] paths) {
        ArrayList<ArrayList<Node>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] p : paths) {
            graph.get(p[0]).add(new Node(p[1], p[2]));
            graph.get(p[1]).add(new Node(p[0], p[2]));
        }

        return graph;
    }


    public static void main(String[] args) {
        Solution T = new Solution();
        Scanner stdIn = new Scanner(System.in);

//        int n = 6;
//        int[][] paths = {{1, 2, 3}, {2, 3, 5}, {2, 4, 2}, {2, 5, 4}, {3, 4, 4}, {4, 5, 3}, {4, 6, 1}, {5, 6, 1}};
//        int[] gates = {1, 3};
//        int[] summits = {5};

        int n = 7;
        int[][] paths = {{1, 4, 4}, {1, 6, 1}, {1, 7, 3}, {2, 5, 2}, {3, 7, 4}, {5, 6, 6}};
        int[] gates = {1};
        int[] summits = {2, 3, 4};

        for (int i : T.solution(n, paths, gates, summits)) {
            System.out.print(i + " ");
        }
    }
}

class Node implements Comparable<Node> {
    int index;
    int intensity;

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

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