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

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

---

2022 카카오 인턴십 기출이다.

출입구에서 출발하여 산봉우리 한 곳을 찍은 뒤 원래의 출입구로 돌아와야 한다.

주어진 간선들은 모두 양방향이기 때문에, 산봉우리에 올라갈 때와 산봉우리에서 내려올 때를 구분하지 않고, 편도 코스의 최소 intensity만 구해주면 된다. (올라갈 때의 intensity) < (내려올 때의 intensity) 라면, 올라간 코스 그대로 내려오는 것이 더 이득이기 때문이다.

여기서는 산봉우리를 출발점으로 잡고, 내려올 때 기준으로 intensity를 구했다.

출발점에서 최소 intensity를 갖는 출입구 노드를 찾아야 하고, 간선에 가중치가 존재하는 상황이므로 다익스트라를 사용하면 쉽게 풀 수 있다.
일반적인 다익스트라는 거리 = (간선 가중치의 누적합)이지만, 여기서의 거리는 간선 가중치의 최댓값이 된다.

---

1. Node 클래스 정의

class Node implements Comparable<Node> {
    int idx;
    int dist;
    public Node(int idx, int dist) {
        this.idx = idx;
        this.dist = dist;
    }
    public int compareTo(Node o) {
        return this.dist - o.dist;
    }
}

 

먼저 (노드 번호, intensity의 최댓값)을 저장하는 Node 클래스를 선언해주었다. PriorityQueue

 

---

2. 출발점 기준으로 다익스트라 실행하기

각 산봉우리를 출발점으로 삼아, 다익스트라를 실행한다.
Priority Queue를 이용해 intensity가 최소인 노드를 우선 탐색했으므로, 출입구에 도착하면 해당 코스가 최소 intensity를 갖는 코스가 된다.

 

int N; // N = n

// graph[i]: i번 노드에서 갈 수 있는 노드의 번호를 저장하는 List
// isGate[i]: i번 노드가 출입구 노드면 true
// isSummit[i]: i번 노드가 산봉우리 노드면 true
List<Node>[] graph;
boolean[] isGate, isSummit;

int findCourse(int start) {
    // 시작 노드 기준으로, i번 노드까지 가는 코스의 거리(=intensity 중 최댓값) 저장
    int[] intensity = new int[N+1];
    Arrays.fill(intensity, Integer.MAX_VALUE);
    PriorityQueue<Node> pq = new PriorityQueue<>();

    pq.add(new Node(start, 0));
    intensity[start] = 0;
    while(!pq.isEmpty()) {
        Node now = pq.poll();

        // 출입구 노드에 도착하면 하산 종료 -> 지나온 간선의 가중치 중 최댓값 반환
        if(isGate[now.idx]) return now.dist;

        // 출발점을 제외한 다른 산봉우리 노드는 방문 불가하므로 skip
        if(now.idx!=start && isSummit[now.idx]) continue;

        for (Node next : graph[now.idx]) {
            int nextIntensity = Math.max(now.dist, next.dist);

            if(intensity[next.idx] <= nextIntensity) continue;

            pq.add(new Node(next.idx, nextIntensity));
            intensity[next.idx] = nextIntensity;
        }
    }

    // 출입구까지 가는 길이 없는 산봉우리인 경우 MAX_VALUE를 반환하여 답이 되는 것을 방지
    return Integer.MAX_VALUE;
}

 

---

3. 전체 코드

import java.util.*;

class Node implements Comparable<Node> {
    int idx;
    int dist;
    public Node(int idx, int dist) {
        this.idx = idx;
        this.dist = dist;
    }
    public int compareTo(Node o) {
        return this.dist - o.dist;
    }
}
class Solution {
    int N;
    List<Node>[] graph;
    boolean[] isGate, isSummit;
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        int[] answer = new int[2];
        N = n;
        graph = new ArrayList[N+1];
        isGate = new boolean[N+1];
        isSummit = new boolean[N+1];
        Arrays.sort(summits);

        for (int i=1; i<=N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i=0; i<gates.length; i++) {
            isGate[gates[i]] = true;
        }
        for (int i=0; i<summits.length; i++) {
            isSummit[summits[i]] = true;
        }

        for (int i=0; i<paths.length; i++) {
            int a = paths[i][0];
            int b = paths[i][1];
            graph[a].add(new Node(b, paths[i][2]));
            graph[b].add(new Node(a, paths[i][2]));
        }

        int minIntensity = Integer.MAX_VALUE;
        int summitIdx = 0;
        for (int i=0; i<summits.length; i++) {
            int intensity = findCourse(summits[i]);
            if(minIntensity > intensity) {
                minIntensity = intensity;
                summitIdx = summits[i];
            }
        }

        answer[0] = summitIdx;
        answer[1] = minIntensity;

        return answer;
    }

    int findCourse(int start) {
        int[] intensity = new int[N+1];
        Arrays.fill(intensity, Integer.MAX_VALUE);
        PriorityQueue<Node> pq = new PriorityQueue<>();

        pq.add(new Node(start, 0));
        intensity[start] = 0;
        while(!pq.isEmpty()) {
            Node now = pq.poll();

            if(isGate[now.idx]) return now.dist;
            if(now.idx!=start && isSummit[now.idx]) continue;

            for (Node next : graph[now.idx]) {
                int nextIntensity = Math.max(now.dist, next.dist);
                if(intensity[next.idx] <= nextIntensity) continue;
                pq.add(new Node(next.idx, nextIntensity));
                intensity[next.idx] = nextIntensity;
            }
        }

        return Integer.MAX_VALUE;
    }
}