[JAVA] Programmers : 등산코스 정하기

문제

프로그래머스

 

오랜만에 글을 작성한다.

그 동안 꾸준히 알고리즘은 학습하고 있었지만 글 작성을 할 여유가 없어서 작성하지 못했는데 이 문제는 해결 방법을 공유해두면 좋을 것 같아서 작성해보려고 한다.

 

문제읽기

XX산은 n개의 지점으로 이루어져있는데 각 지점은 1 ~ n 까지 번호가 붙어있고 해당 지점들은 출입구, 쉼터, 산봉우리 중 하나이다.

각 지점으로 이동할 때 등산로를 이용해야하는데 이 때 등산로별로 소요되는 시간이 다르다.

 

이 때 각 지점에 방문할 때마다 휴식을 취할 수 있는데 휴식 없이 이동해야하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity라고 부르기로 하였다.

등산 코스는 하나의 출입구에서 시작해서 산봉우리를 방문하고 원래의 출입구로 돌아오는 코스여야한다.

이러한 규칙을 지키면서 intensity가 최소가 되도록 등산코스를 정하자..!

 

 

---

 

위 문제를 읽으면서 intensity를 이해하는데 시간이 조금 소요했는데 각 지점별로 걸리는 시간이 1 - 2 - 3 - 2 - 1 이라면 가장 소요시간이 길었던 3이 intensity가 되는 것이고 해당 intensity가 가장 짧은 등산코스를 찾으면 되는 것이다.

 

해결방법

처음에 KAKAO TECH INTERNSHIP 에 응시하면서 먼저 만나보았었던 문제였는데, 그 당시에는 풀지 못했었다.

당시 풀이는 산 정상까지 올라간다음 내려오는 것까지 생각하고 루트를 찾았는데 정확한 답이 출력되지 않았고 시간도 오래걸렸다.

 

따로 스터디를 진행하면서 이 문제를 다시 보게 되었는데, 3시간 정도 고민한 결과 답을 찾았다.

산봉우리까지 방문하고 내려오는 길이 중복되면 안된다는 조건이 없기때문에 처음 출발지에서 산봉우리까지의 등산코스만 찾으면 된다.내려올 때 같은 코스로 내려오게되면 intensity도 동일하기 때문..!

 

그래서 출발지에서 산봉우리까지 intensity 값이 작은 등산 코스를 찾아 올라가면되는데 해당하는 값을 찾기 위해 다익스트라를 사용하면된다.

그래서 다익스트라 배열에는 각 지점까지 도달할 수 있는 가장 작은 intensity값이 저장되게 될 것이다.

 

먼저 각 등산 코스에 대한 양방향 인접리스트를 작성하고

출발지를 우선순위큐에 넣어 탐색을 시작한다.

 

탐색하면서 산봉우리거나 현재 위치의 intensity값이 내가 가진 intensity값(node.time)보다 작다면 더 이상 탐색하지 않는다.

그렇지 않다면 intensity값을 비교하면서 다익스트라 배열에 저장된 값보다 새로운 등산코스가 intensity가 작을 경우 값을 갱신하며 탐색을 진행해준다.

 

탐색이 끝났을 때 문제의 조건이 하나 더 있어서 정렬을 해주어야한다.

만약 산봉우리 별로 intensity값이 동일한 등산 코스가 존재한다면 가장 산봉우리 번호가 작은 등산코스를 선택해야하기 때문이다.

 

그래서 정렬을하고 값을 찾아 반환해주면된다.

주석에도 설명이 추가되어있으니 참고해주길 바란다.

 

코드

import java.util.*;

class Solution {
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        // 각 지점에 대한 인접리스트 생성
        ArrayList<Node> list[] = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) list[i] = new ArrayList<>();
        
        for (int i = 0; i < paths.length; i++) {
            int start = paths[i][0];
            int end = paths[i][1];
            int w = paths[i][2];
            
            list[start].add(new Node(end, w));
            list[end].add(new Node(start, w));
        }

        // 다익스트라 준비
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        // 산봉우리 확인용
        boolean[] isSummit = new boolean[n + 1];
        for (int i = 0; i < summits.length; i++) {
            isSummit[summits[i]] = true;
        }
        
        // 출발지만 큐에 넣어준다
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 0; i < gates.length; i++) {
            pq.offer(new Node(gates[i], 0));
            dist[gates[i]] = 0;
        }
        
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            
            // 산봉우리거나 현재 INTENSITY가 더 크다면 넘김
            if (isSummit[node.next] || node.time > dist[node.next]) continue;

            for (int i = 0; i < list[node.next].size(); i++) { // foreach로 바꾸면 단순화됨
                int next = list[node.next].get(i).next;
                int time = list[node.next].get(i).time;
                
                int intensity = Math.max(node.time, time); // INTENSITY 값을 선택
                if (intensity < dist[next]) {
                    dist[next] = intensity;
                    pq.offer(new Node(next, dist[next]));
                }
            }
        }
        
        // 답 찾기
        Arrays.sort(summits); // INTENSITY가 동일하다면 산봉우리 번호가 제일 낮은 등산코스를 선택해야하므로

        int[] answer = new int[]{0, Integer.MAX_VALUE};

        for (int summit : summits) {
            if (dist[summit] < answer[1]) {
                answer[1] = Math.min(answer[1], dist[summit]);
                answer[0] = summit;
            }
        }
        return answer;
    }
    
    static class Node implements Comparable<Node> {
        int next;
        int time;
        
        Node (int next, int time) {
            this.next = next;
            this.time = time;
        }
        
        @Override
        public int compareTo(Node o) {
            return time - o.time;
        }
    }
}