프로그래머스 등산코스 정하기 자바 풀이

문제 링크

문제 풀이 시간 : 1시간15분

문제 요약

산의 지점들 중 출입구 → 산봉우리 → 출입구로만 이동해야 함.
경로에서 지나는 등산로 시간 중 가장 큰 값 = intensity.
모든 산봉우리 중, intensity가 가장 작은 산봉우리를 찾는다.(동률이면 번호가 작은 것)

문제 풀이

이 문제는 얼핏 보면

“출입구에서 각 산봉우리까지 왕복하며 최댓값이 최소가 되는 경로”

→ Minimax Path 문제로 보인다.

즉, 단순한 최단 거리(다익스트라)처럼 간선들의 합을 최소화하는 것이 아니라

경로 중 가장 큰 간선(시간)을 최소화해야 한다.

그래서 처음엔 산봉우리에서 BFS로 출입구까지 탐색하면서

최댓값을 갱신해가는 방식을 시도했다.

하지만, 이 방식은 문제가 많았고 실제로 오답이 나왔다.

(→ 뒤에서 “실패 코드”로 정리)

핵심 아이디어

목표: intensity = 경로 중 최대 간선 가중치를 최소화
이때, 출입구는 여러 곳일 수 있고
즉,
또한, 산봉우리에 도착하면 더 이상 확장할 필요가 없다.

실패 접근

처음 시도할 때는,

각 산봉우리(summit)에서 출발 → 출입구까지 도달

할 때 발생하는 intensity를 계산하는 방식이었다.

java

for (각 summit) {
    BFS → gate에 도달할 때까지 탐색
    intensity = 경로 내 최대 간선
    최소값 갱신
}

겉으로 보면 될 것 같았으나, 실제로는

모든 산봉우리마다 BFS/Dijkstra → 비효율
탐색 방향 제약이 사실상 없어

그래서 조건을 제대로 만족시키기 어렵고

시간/메모리도 비효율적이라 결국 실패했다.

실패 코드

java

for(int i=0;i<summits.length;i++){
    int[] dist = new int[n+1];
    boolean[] visited = new boolean[n+1];
    int s = summits[i];
    Arrays.fill(dist,Integer.MAX_VALUE);
    dist[s] = 0;

    Queue<Node> q = new ArrayDeque<>();
    q.add(new Node(s,0));

    while(!q.isEmpty()){
        Node now = q.poll();
        if(now.dist>dist[now.num])
            continue;
        dist[now.num] = now.dist;

        if(gate.contains(now.num)){
            if(answer[1]<now.dist)
                continue;
            answer[0] = s;
            answer[1] = now.dist;
            continue;
        }

        for(Node next : arr[now.num]){
            int nd = Math.max(now.dist, next.dist);
            if(dist[next.num]<nd)
                continue;
            q.add(new Node(next.num, nd));
        }
    }
}

다중 시작점 다익스트라 + Max Edge Cost 누적 방식

출입구들을 모두 시작점으로 하여intensity[node] = 그 지점까지 도달할 때의 최소 intensity로 정의하고 갱신해간다.
일반적인 다익스트라는 cost = prev_cost + edge이지만,
또한, 도중에 산봉우리에 도착하면 그 노드는 확장하지 않는다.
최종적으로 모든 산봉우리 중 intensity[s]가 가장 작은 산봉우리를 선택 (동률 시 번호가 작은 것)

왜 출입구에서 출발해야 하나?

문제 규칙상
즉, 코스의 진입과 탈출은 항상 출입구.
그러므로, 출입구에서 시작해 각 지점까지 intensity를 갱신해가는 게 자연스러움.

정답 코드

java

import java.util.*;

class Solution {
    public class Node{
        public int num;
        public int dist;

        public Node(int num, int dist){
            this.num = num;
            this.dist = dist;
        }
    }

    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        int[] answer = {Integer.MAX_VALUE, Integer.MAX_VALUE};

        List<Node>[] arr = new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            arr[i] = new ArrayList<>();
        }

        Set<Integer> summit = new HashSet<>();
        for(int s : summits){
            summit.add(s);
        }

        for(int[] p : paths){
            int f = p[0], t = p[1], d = p[2];
            arr[f].add(new Node(t, d));
            arr[t].add(new Node(f, d));
        }

        PriorityQueue<Node> pq = new PriorityQueue<>((a,b)->a.dist-b.dist);
        int[] intensity = new int[n+1];
        Arrays.fill(intensity, Integer.MAX_VALUE);

        for(int g : gates){
            intensity[g] = 0;
            pq.add(new Node(g, 0));
        }

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

            if(intensity[now.num] < now.dist)
                continue;
            if(summit.contains(now.num))
                continue;

            for(Node next : arr[now.num]){
                int cost = Math.max(now.dist, next.dist);
                if(cost < intensity[next.num]){
                    intensity[next.num] = cost;
                    pq.add(new Node(next.num, cost));
                }
            }
        }

        Arrays.sort(summits);
        for(int s : summits){
            if(intensity[s] < answer[1]){
                answer[0] = s;
                answer[1] = intensity[s];
            }
        }

        return answer;
    }
}

등산코스 정하기

문제 풀이 시간 : 1시간15분

문제 요약

문제 풀이

핵심 아이디어

실패 접근

실패 코드

다중 시작점 다익스트라 + Max Edge Cost 누적 방식

왜 출입구에서 출발해야 하나?

정답 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기