골드에그

1. 문제요약

코딩테스트 연습 - 등산코스 정하기 | 프로그래머스 스쿨 (programmers.co.kr)

출입구에서 산봉우리까지 갔다가 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 한다.

등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity 라고 할 때 이 intensity 가 가장 짧은 코스를 찾아라. (등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 한다.)

2. 문제예제

등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같다.

각 경로의 가중치가 가장 큰 값이 3 이며, 이 보다 intensity가 낮은 등산코스는 없다.

3. 팩트추출

Fact 1 : Dijkstra 다이젝스트라 알고리즘처럼 항상 최단 거리를 선택한다면, 경로의 intensity 배열은 항상 단조 증가 형태이다. 이 점을 활용하면 출발점에서 산봉우리까지 갔다가 다시 출발점으로 돌아오지 않아도 된다. 출발점에서 산봉우리까지 가는 반쪽짜리 최단 경로만 찾으면 된다. 출발 경로와 회귀 경로가 틀릴 수 있을지 언정 intensity 는 같을 것이기 때문이다. 이 문제에서는 경로를 구하라고 하지 않았으므로 가능하다. => 따라서 큐에 꺼낸 위치가 산봉우리라면 탐색을 종료한다.

Fact 2 : Fact 1 과 마찬가지로 경로를 구하라고 하지는 않았으므로, 출발점에서 동시에 출발하여 intensity 배열을 수정하여도 상관이 없다. 문제에서 요구하는 정답은 산봉우리와 그 산봉우리의 intensity 이다. 그러니까 어느 출발점에서 출발하여도 도착지점의 intensity 가 최소가 되는 경로만 찾으면 된다. 따라서 우선순위 큐에 출발지점을 모두 넣어놓고 시작한다.

Fact 3 : 일반적인 Dijkstra 다이젝스트라 알고리즘과 다른 점은 각 지점의 비용을 합한 거리가 최소가 되는 경로를 찾는 것이 아니라 각 구간의 최대 비용이 최소가 되는 경로를 찾는 것이다. 따라서 아래와 같이 로직을 수정한다.

if(dist[adjNode.to] > curNode.weight + adjNode.weight){
	dist[adjNode.to] = curNode.weight + adjNode.weight;
}

↓↓↓↓↓↓

if (dist[adjNode.to] > Math.max(curNode.weight, adjNode.weight)) {
	dist[adjNode.to] = effort;
}

Fact 4 : 산봉우리까지 가는 intensity 가 같은 경로가 여러 개라면, 산봉우리의 번호가 가장 작은 것을 반환하라고 지문에서 나와있으므로 산봉우리-intensity 배열에서 최소값을 찾을 때 산봉우리 배열을 먼저 정렬해야 한다.

4. 문제전략

팩트추출에서 소개한 다이젝스트라 변형 알고리즘을 사용하면 된다.

5. 소스코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    static class Node implements Comparable<Node> {
        int index;
        int effort;
        public Node(int index, int effort) {
            this.index = index;
            this.effort = effort;
        }
        @Override
        public int compareTo(Node o) {
            return this.effort - o.effort;
        }
    }
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int[] efforts;
    static int[] gatesSave, summitsSave;
    private static void initGraph(int v, int[][] data) {
        for(int i=0; i < v+1; i++){
            graph.add(new ArrayList<>());
        }
        for (int[] datum : data) {
            graph.get(datum[0]).add(new Node(datum[1], datum[2]));
            graph.get(datum[1]).add(new Node(datum[0], datum[2]));
        }
        efforts = new int[v+1];
        for (int i = 1; i < v+1; i++) {
            efforts[i] = Integer.MAX_VALUE;
        }
    }

    private static int[] dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        // 시작지점 삽입
        for (int gate : gatesSave) {
            pq.offer(new Node(gate, 0));
            efforts[gate] = 0;
        }

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            if (isSummit(curNode.index))
                continue;
            if (efforts[curNode.index] < curNode.effort) {
                continue;
            }
            for (Node adjNode : graph.get(curNode.index)) {
                int effort = (adjNode.effort == Integer.MAX_VALUE) ? curNode.effort : Math.max(curNode.effort, adjNode.effort);
                if (efforts[adjNode.index] > effort) {
                    efforts[adjNode.index] = effort;
                    pq.offer(new Node(adjNode.index, efforts[adjNode.index]));
                }
            }
        }

        Arrays.sort(summitsSave);
        int index = -1;
        int minEffort = Integer.MAX_VALUE;
        for (int summit : summitsSave) {
            if (efforts[summit] < minEffort) {
                minEffort = efforts[summit];
                index = summit;
            }
        }
        return new int[]{index, minEffort};
    }

    private static boolean isSummit(int num) {
        for (int summit : summitsSave) {
            if (num == summit) return true;
        }
        return false;
    }

    public static int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        gatesSave = gates;
        summitsSave = summits;
        initGraph(n, paths);
        return dijkstra();
    }
}