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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/118669

[이 문제는 프로그래머스에서 푼 문제입니다.]
이 문제는 우선순위 큐와 Hash 클래스들을 이용하여 풀 수 있습니다. 이 문제는 복잡해보이는 문제를 단순화시키면 좀 더 이해하기 쉽습니다. intensity의 경우 출발점에서 목적지까지 이동하는 도중 절대로 감소하지 않습니다. 따라서 문제에서 구하고자 하는 intensity가 최소가 되는 등산 코스는 각 위치 별 intensity를 이동하면서 계속 계산해준 후 목적지에 도착했을 때 여러 경로 중 가장 작은 값을 출력하면 됩니다.

이 때 intensity를 최소로 하려면 여러 경로 중 가장 가중치가 적은 경로로 이동해야 합니다. 이는 우선순위 큐를 이용하여 원소들을 정렬시켜 poll() 시 가장 작은 값이 나오도록 진행합니다. 여기서 주의할 점은 intensity가 같은 경우 번호가 더 작은 코스를 리턴해야 하니 이 부분도 같이 정렬 기준에 포함시키면 되겠습니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        // dp[i] = i번 노드에서의 최소 intensity
        int[] intensities = new int[n+1];
        // 최솟값이 저장되어야 하므로 최댓값으로 초기화
        Arrays.fill(intensities, Integer.MAX_VALUE);

        // 현재 노드를 이동, PQ를 사용하여 최솟값을 향하도록
        PriorityQueue<Graph> map = new PriorityQueue<>();
        // 지나온 노드 체크
        HashSet<Integer> check = new HashSet<>();
        // 정상 데이터 (탐색 시간 단축 위해)
        HashSet<Integer> arrival = new HashSet<>();
        // 노드 별 간선 현황과 가중치 그래프 (탐색 시간 단축 위해 HashMap 사용)
        HashMap<Integer, ArrayList<Graph>> graph = new HashMap<>();

        Graph answer = new Graph(-1,-1,Integer.MAX_VALUE);

        // 그래프 생성
        for(int i=0;i<paths.length;i++){
            int start = paths[i][0];
            int arrive = paths[i][1];
            int time = paths[i][2];

            Graph g1 = new Graph(start,arrive,time);
            Graph g2 = new Graph(arrive,start,time);

            // start 또는 arrive 노드가 초기화되지 않았다면 초기화
            if(!graph.containsKey(start)) graph.put(start,new ArrayList<>());
            if(!graph.containsKey(arrive)) graph.put(arrive,new ArrayList<>());

            // 값 추가
            graph.get(start).add(g1);
            graph.get(arrive).add(g2);
        }

        // 정상 데이터 추가
        for(int i=0;i<summits.length;i++) arrival.add(summits[i]);

        // 출입구 데이터 추가 (HashSet 이용)
        for(int i=0;i<gates.length;i++){
            // 출발 지점이므로 map에 추가
            map.addAll(graph.get(gates[i]));
            // 지나왔으므로 check
            check.add(gates[i]);
            // 출발 지점이므로 intensity가 존재하지 않아 0 추가
            intensities[gates[i]] = 0;
        }

        // 현재 모든 출입구를 탐색
        while (!map.isEmpty()){
            Graph curr = map.poll();

            // 만약 현재 노드가 이미 방문한 노드라면 패스
            if(check.contains(curr.to)) continue;

            // intensity는 지금까지 지나온 intensity와 현재 간선의 가중치 중 최댓값
            int intensity = Math.max(intensities[curr.from], curr.weight);
            // 만약 현재 노드의 초기 intensity가 지금까지 지나온 intensity보다 크다면 지나온 값으로 변경 (최솟값 세팅)
            if(intensity < intensities[curr.to]) intensities[curr.to] = intensity;

            // 만약 현재 노드가 정상이라면 answer값과 비교하여 더 작은 값 넣기
            if(arrival.contains(curr.to)){
                curr = new Graph(0, curr.to, intensity);

                // 비교 1. 더 작은 intensity
                // 비교 2. 더 작은 노드(같은 intensity일 경우)
                if(answer.compareTo(curr) >0) answer = curr;
            }
            // 정상이 아니라면 map에 추가 후 check
            else{
                map.addAll(graph.get(curr.to));
                check.add(curr.to);
            }

        }

        return new int[]{answer.to,answer.weight};
    }
}

class Graph implements Comparable<Graph> {
    int from, to, weight;

    Graph(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    @Override
    // 가중치가 낮은 노드로 정렬, 같은 가중치일 경우 노드의 오름차순으로 정렬
    public int compareTo(Graph o) {
        if (this.weight == o.weight)
            return Integer.compare(this.to, o.to);
        return Integer.compare(this.weight, o.weight);
    }
}