[프로그래머스 / JAVA] 등산코스 정하기

문제

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

접근

무방향 그래프에서 최단 경로 구하기와 유사한 문제이다.

보통의 문제는 목적지까지의 가중치 합이 최소인 경우를 구하는 것이 대부분이다. 하지만, 이 문제에선 목적지까지의 경로에서 지나온 가중치들 중 최댓값을 intensity라고 부르고, 이 intensity가 최소인 경로를 구해야 한다.

처음엔 문제 이해도 못해서 애를 먹었다.

기존의 최단 경로 알고리즘에선 가중치의 합을 테이블에 저장 및 비교하며 경로를 구했다면, 이 문제에선 가중치의 최댓값을 테이블에 저장하여 해결할 수 있을 것이다.
결국, 이 문제도 최단 경로를 구하는 문제와 비슷하게 접근해 볼 수 있겠다.

음수 사이클이 존재하지 않기 때문에 다익스트라 알고리즘을 사용했다.

풀이

import java.util.*;

class Solution {
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        // 그래프 생성
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<int[]>());
        }
        for (int[] path : paths) {
            graph.get(path[0]).add(new int[]{path[1], path[2]});
            graph.get(path[1]).add(new int[]{path[0], path[2]});
        }

        // 산봉우리 판별 배열 생성
        boolean[] isSummit = new boolean[n + 1];
        for (int summit : summits) {
            isSummit[summit] = true;
        }
        
        // pq에 시작점 세팅
        int[] intensity = new int[n + 1];
        Arrays.fill(intensity, Integer.MAX_VALUE);
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        for (int gate : gates) {
            pq.add(new int[]{gate, 0});
            intensity[gate] = 0;
        }
        
        // 다익스트라        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currentNode = current[0];
            int currentIntensity = current[1];
            
            if (isSummit[currentNode]) continue;
            // 불필요한 노드 방문을 제외하여 시간 단축
            if (currentIntensity > intensity[currentNode]) continue;
            
            for (int[] node : graph.get(currentNode)) {
                int nextNode = node[0];
                int nextWeight = node[1];
                
                int nextIntensity = Math.max(currentIntensity, nextWeight);
                
                if (intensity[nextNode] > nextIntensity) {
                    intensity[nextNode] = nextIntensity;
                    pq.offer(new int[]{nextNode, nextIntensity});
                }
            }
        }
        
        // 산봉우리 중 intensity 값이 가장 작은 것
        Arrays.sort(summits);
        int[] answer = new int[]{0, Integer.MAX_VALUE};
        for (int summit : summits) {
            if (answer[1] > intensity[summit]) {
                answer[0] = summit;
                answer[1] = intensity[summit];
            }
        }
        
        return answer;
    }
}

정리

최초 제출에서 TC 21번 - 시간 초과가 발생했다.

기존의 다익스트라 알고리즘

// 다익스트라        
while (!pq.isEmpty()) {
    int[] current = pq.poll();
    int currentNode = current[0];
    int currentIntensity = current[1];
    
    if (isSummit[currentNode]) continue;
    
    for (int[] node : graph.get(currentNode)) {
        int nextNode = node[0];
        int nextWeight = node[1];
        
        int nextIntensity = Math.max(currentIntensity, nextWeight);
        
        if (intensity[nextNode] > nextIntensity) {
            intensity[nextNode] = nextIntensity;
            pq.offer(new int[]{nextNode, nextIntensity});
        }
    }
}

이 코드에선 방문하지 않아도 되는 노드를 방문하는 문제가 있었다.

문제점

1. intensity[currentNode]에는 해당 노드에 방문하는 여러 경로 중, intensity의 최솟값이 저장되어 있음.
2. currentIntensity 값은 현재 경로의 가장 큰 가중치 값. 즉, 현재 경로의 intensity 값이 저장되어 있음.
3. currentIntensity > intensity[currentNode]이면, 현재 경로로 currentNode를 방문하는 것은 의미가 없기 때문에 제외 시킬 수 있음.
   
   

변경된 다익스트라 알고리즘

// 다익스트라        
while (!pq.isEmpty()) {
    int[] current = pq.poll();
    int currentNode = current[0];
    int currentIntensity = current[1];

    if (isSummit[currentNode]) continue;
    // 불필요한 노드 방문을 제외하여 시간 단축
    if (currentIntensity > intensity[currentNode]) continue;

    for (int[] node : graph.get(currentNode)) {
        int nextNode = node[0];
        int nextWeight = node[1];

        int nextIntensity = Math.max(currentIntensity, nextWeight);

        if (intensity[nextNode] > nextIntensity) {
            intensity[nextNode] = nextIntensity;
            pq.offer(new int[]{nextNode, nextIntensity});
        }
    }
}