[ 99클럽/챌린저 ] 4일차 TIL : 등산코드 정하기

---

• 다시 풀기 필요

---

문제 요약

n개의 지점으로 이뤄진 등산 코스는 출발점과 정상인 산봉우리, 등산로로 이뤄져 있다. 각 지점을 지날 때마다 intensity라 불리는 시간이 소요된다. 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래 출입구로 돌아오는 등산코드를 선택할 것이다.
즉, 등산코스와 출입구는 처음과 끝에서 한 번만, 산봉우리는 한 번만 포함되어야 한다.
해당 등산코드를 대표하는 intensity는 해당 코스에서 가장 큰 intensity가 된다.
이 규칙을 지키며, 여러 등산 코스 중 intensity가 최소가 되는 등산코스를 정하자.
만일 intensity가 같은 코스가 여러 개일 경우, 그 중 산봉우리 번호가 가장 낮은 등산코스를 선택하자.

[ 예시 ]

n	paths	gates	summits	result
6	[[1, 2, 3], [2, 3, 5], [2, 4, 2], [2, 5, 4], [3, 4, 4], [4, 5, 3], [4, 6, 1], [5, 6, 1]]	[1, 3]	[5]	[5, 3]
7	[[1, 4, 4], [1, 6, 1], [1, 7, 3], [2, 5, 2], [3, 7, 4], [5, 6, 6]]	[1]	[2, 3, 4]	[3, 4]

[ 제약 조건 ]

• 2 ≤ n ≤ 50,000
• n-1 ≤ paths의 길이 ≤ 200,000
• paths는 [i, j, w] 형태이다.
  • i번 지점과 j번 지점을 연결하는 등산로를 의미
  • w는 두 지점 사이에 소요된 이동 시간
  • 1 ≤ w ≤ 10,000,000

[ 프로그래머스 ]

• Java
• 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/118669

---

풀이

• 등산로를 양방향으로 이동 가능하며, 가중치가 양수임으로 Dijkstar 알고리즘 사용
• 문제의 핵심은 일단 산봉우리에 도착하면 다시 돌아오는 길을 계산할 필요가 없다는 것이다.
  왜? 이동했던 경로 내려와야 intensity가 최소가 되기 때문
• 또한, 입구와 산봉우리는 단방향, 그외 경로는 양방향 그래프로 만드는 것이다.

(1) 노드와 가중치로 이뤄진 Node 클래스 선언
(2) paths의 각 지점을 경우에 맞게 양방향 혹은 단뱡향으로 저장

• 출입구일 경우, 다른 곳으로만 이동 가능한 단뱡항으로 저장
• 산봉우리일 경우, 특정 한 곳에서 산봉우리로 가는 단뱡향으로 저장
  ※ 이렇게 해야 등산코스와 출입구는 처음과 끝에서 한 번만, 산봉우리는 한 번만 포함되어야 한다. 조건을 충족시킬 수 있다.
• 일반 등산로는 양방향으로 저장

(3) BFS를 위해 모든 출발지를 Queue에 삽입
(4) 현 지점에 도달하기까지 계산된 가장 긴 intensity와 다음 지점으로 이동시 소요되는 intensity 중 가장 큰 값을 dist에 저장
※ 결국 문제에서 요구하는 것은 선택된 등산 코스의 가장 긴 intensity이기 때문에

(5) 다른 등산 코스에서 다음 지점에 도달하기까지 갖게 된 가장 intensity와 비교

• 예를 들어, 현재 지점이 A, 다음 지점이 C, C로 올 수 있는 다른 코스 B가 있다면, A->C의 intensity와 B->C의 intensity를 비교
  (6) 만약 더 크다면, 다음 지점의 intensity배열을 해당 값으로 저장 :다익스트라

(7) Queue에 다음 지점 삽입
(8) summits 배열 오름차순으로 정렬
※ intensity가 동일할 경우, 산봉우리가 가장 낮은 코스를 선택해야하기 때문
(9) 산봉우리에 도달할 때까지 가장 긴 intensity가 intensity[summit]에 저장되기 때문에, 각 산봉우리 별 가장 짧은 intensity 판별 및 해당 산봉우리 저장
(10) int[] 배열로 반환

---

Code

import java.util.*;
import java.math.*;

class Solution {
    static List<List<Node>> graph;
    static final int INF = 10_000_001;
    
    private static class Node {
        int e, w;
        Node(int e, int w) {
            this.e = e;
            this.w = w;
        }
    }
    
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        int[] answer = {};
        graph = new ArrayList<>();
        
        for(int i=0;i<n+1;i++) {
            graph.add(new ArrayList<>());
        }
        
        for(int[] i : paths) {
            int start = i[0];
            int end = i[1];
            int weight = i[2];
            
            if (isGate(start, gates) || isSummit(end, summits)) {
                graph.get(start).add(new Node(end, weight));
            } else if (isGate(end, gates) || isSummit(start, summits)) {
                graph.get(end).add(new Node(start, weight));
            } else {
                // 일반 등산로일 경우, 양방향
                graph.get(start).add(new Node(end, weight));
                graph.get(end).add(new Node(start, weight));
            }
        }
        
        
        return dijkstra(n, gates, summits);
    }
    
    private static int[] dijkstra(int n, int[] gates, int[] summits) {
        Queue<Node> queue = new LinkedList<>();
        int[] intensity = new int[n+1];
        
        Arrays.fill(intensity, INF);
        
        for(int i: gates) {
            queue.add(new Node(i, 0));
            intensity[i] = 0;
        }
        
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            
            // 현 노드의 가중치가 계산된 노드의 가중치보다 크다면, 최소 갱신이 안 됨으로 스킵
            if (curNode.w > intensity[curNode.e])
                continue;
            
            // 연결된 노드 탐색
            for(int i=0;i<graph.get(curNode.e).size(); i++) {
                Node next = graph.get(curNode.e).get(i);
                
                int dist = Math.max(intensity[curNode.e], next.w);
                if (intensity[next.e] > dist) {
                    intensity[next.e] = dist;
                    queue.add(new Node(next.e, dist));
                }
            }
        }
        
        int summitIndex = INF;
        int lowerWeight = INF;
        
        // intensity 동일할 경우, 산봉우리 번호가 가장 낮은 코스 선택
        Arrays.sort(summits);
        
        for(int summit : summits) {
            if (intensity[summit] < lowerWeight) {
                lowerWeight = intensity[summit];
                summitIndex = summit;
            }
        }
        
        return new int[]{summitIndex, lowerWeight};
    }
    
    private static boolean isSummit(int x, int[] summits) {
        for(int s : summits) {
            if (s == x)
                return true;
        }
        return false;
    }
    
    private static boolean isGate(int x, int[] gates) {
        for(int g : gates) {
            if (g == x)
                return true;
        }
        return false;
    }
}

---

시도

• summit과 gate를 섞은 2중 반복문
  각 산봉우리와 출발지별 Dijkstra를 시도하려 했으나 미숙하여 해결하지 못 했다.

---

느낀점

Dijkstra 이론만 공부하고, 처음 접해본 문제여서 그런지 감은 잡히는데 어떻게 풀어나갈지 해답을 찾지 못 했다. 그래서 여러 시도에 도전하기보단 이 문제를 통해 다익스트라의 흐름과 응용 방식을 터득하고자 했다.
그래서 4일차 TIL인데 5일차에 쓰고 있다..하하..
처음 접했을 때 어려웠고, 다른 분들 풀이를 봤을 땐 더 어려웠다. 내용을 정리하고, 하나하나 대입하면서 여러 시도 끝에 80% 정도는 이해했지만 완벽히 이해하진 못 했다.
다음에 다시 풀어봐야겠다.