Programmers - 등산 코스 정하기 with JAVA

 

 

로직

1. 양방향 맵 생성

2. 산봉우리마다 확인

3. 우선순위 큐를 통해 가장 비용이 짧은순으로 처리

- 우선 순위 큐는 비용순으로 처리

- 방문 처리

- 봉우리마다 가장 가까운 출발지 방문시 바로 종료

(비용순으로 처리하고 출발지에 번호는 상관없기에 종료 가능)

- 중간비용이 이미 정답보다 크다면 종료

(예를 들어, 산봉우리 A처리 후 최소값이 5라고 가정, 산봉우리 B 처리 중 이미 비용이 5 이상이라면 더이상 처리할 필요없어짐.)

4. 비용이 가장 작으면서 산봉우리 번호가 가장 작은 구역 반환

 

 

 

코드

import java.util.*;
class Solution {
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        int[] answer = new int[2];
        answer[0] = (int)1e9;
        answer[1] = (int)1e9;
        List<List<List<Integer>>> map = new ArrayList<>();
        for(int i=0; i<n+1; i++){
            map.add(new ArrayList<>());
        }
        for(int[] path : paths){
            map.get(path[0]).add(Arrays.asList(path[1], path[2]));
            map.get(path[1]).add(Arrays.asList(path[0], path[2]));
        }
        for(int goal : summits){
            boolean[] visited = new boolean[n+1];
            PriorityQueue<List<Integer>> queue 
                = new PriorityQueue<>(Comparator.comparing(arr -> arr.get(0)));
            queue.add(Arrays.asList(0, goal));
            while(queue.size() > 0){
                List<Integer> now = queue.poll();
                int cost = now.get(0);
                int num = now.get(1);
                // 수정
                if(cost > answer[1]){
                    break;
                }
                if(Arrays.stream(gates).anyMatch(value->value==num)){
                    if(cost == answer[1]){
                        answer[0] = Math.min(goal, answer[0]);
                    }
                    if(cost < answer[1]){
                        answer[0] = goal;
                        answer[1] = cost;
                    }
                    break;
                }
                if(visited[num]){
                    continue;
                }
                visited[num] = true;
                for(List<Integer> next : map.get(num)){
                    int nextNum = next.get(0);
                    int nextCost = next.get(1);
                    if(Arrays.stream(summits).anyMatch(value->value==nextNum)){
                        continue;
                    }
                    // 수정
                    if(visited[nextNum]){
                        continue;
                    }
                    queue.add(Arrays.asList(Math.max(cost, nextCost), nextNum));
                }
            }
        }
        return answer;
    }
}