등산코스 정하기

XX산의 지점 수 n, 각 등산로의 정보를 담은 2차원 정수 배열 paths, 출입구들의 번호가 담긴 정수 배열 gates, 산봉우리들의 번호가 담긴 정수 배열 summits가 매개변수로 주어집니다. 이때, intensity가 최소가 되는 등산코스에 포함된 산봉우리 번호와 intensity의 최솟값을 차례대로 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요. intensity가 최소가 되는 등산코스가 여러 개라면 그중 산봉우리의 번호가 가장 낮은 등산코스를 선택합니다.

제한사항
2 ≤ n ≤ 50,000
n - 1 ≤ paths의 길이 ≤ 200,000
paths의 원소는 [i, j, w] 형태입니다.
i번 지점과 j번 지점을 연결하는 등산로가 있다는 뜻입니다.
w는 두 지점 사이를 이동하는 데 걸리는 시간입니다.
1 ≤ i < j ≤ n
1 ≤ w ≤ 10,000,000
서로 다른 두 지점을 직접 연결하는 등산로는 최대 1개입니다.
1 ≤ gates의 길이 ≤ n
1 ≤ gates의 원소 ≤ n
gates의 원소는 해당 지점이 출입구임을 나타냅니다.
1 ≤ summits의 길이 ≤ n
1 ≤ summits의 원소 ≤ n
summits의 원소는 해당 지점이 산봉우리임을 나타냅니다.
출입구이면서 동시에 산봉우리인 지점은 없습니다.
gates와 summits에 등장하지 않은 지점은 모두 쉼터입니다.
임의의 두 지점 사이에 이동 가능한 경로가 항상 존재합니다.
return 하는 배열은 [산봉우리의 번호, intensity의 최솟값] 순서여야 합니다.

###처음한 생각
산봉우리는 1번 그리고 출구로 돌아와야하지만 필요한 배열은 산봉우리의 번호,거리의 최솟값이기에 돌아오는 코드를 짜지않아도 된다.
산봉우리에 도달한 시점에서 그 이후는 신경쓰지않아도된다.
다른 출구로 도착한다면 그 값을 버려야한다.
BFS를 통해서 전부 순회가 가능해보인다. 다만 산봉우리,출구,그리고 다음 intensity가 현재 값보다 작다면 그 node값은 더이상 q로 돌릴필요가 없다.

코드

import java.util.*;
class Solution {
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        HashSet<Integer> summit = new HashSet<>();
        HashSet<Integer> gate = new HashSet<>();
        Queue<Node> pq = new LinkedList<>();
        int[] intensity = new int[n+1];
        Arrays.fill(intensity,Integer.MAX_VALUE);
        Arrays.sort(summits);
        //node생성
        List<Node>[] list = new ArrayList[n+1];
        //노드 초기화
        for(int i=0;i<n+1;i++){
            list[i] = new ArrayList<>();
        }
        
        //인접리스트 생성
        for(int[] i: paths){
            list[i[0]].add(new Node(i[1],i[2]));
            list[i[1]].add(new Node(i[0],i[2]));
        }
        
        //summit 정렬 해시화
        for(int i : summits){
            summit.add(i);
        }
        for(int i : gates){
            gate.add(i);
            pq.add(new Node(i,0));
            intensity[i] = 0;
        }
        //다잌스트라
       
        dij(list,pq,summit,gate,intensity);
        int index = -1;
        int max = Integer.MAX_VALUE;
        for(int i : summits){
            if(max>intensity[i]){
                index= i;
                max= intensity[i];
            }
        }
        return new int[]{index, max};
    }
    void dij(List<Node>[] list,Queue<Node> pq,HashSet<Integer> summit,HashSet<Integer> gate,int[] intensity){
        while(!pq.isEmpty()){
            
            Node node = pq.poll();
            
            if(summit.contains(node.index)) continue;
            if(node.value>intensity[node.index]) continue;
            
            for(Node next : list[node.index]){
                
                if(gate.contains(next.index)) continue;
                
                int tmp =Math.max(node.value,next.value);
                
                if(intensity[next.index]>tmp){                 
                    intensity[next.index] = tmp;
                    pq.add(new Node(next.index,intensity[next.index]));
                }
               
            }
        }
    }
    class Node  {
        int index;
        int value;
        
        Node(int index,int value){
            this.index= index;
            this.value= value;
        }
       
    }
}

다잌스트라 문제이다. 그걸 안다면. 그냥 구현만 하면 해결되는 문제였다.
인접리스트와 큐를 사용할줄 알고 값의 최적화를 위한 해시를 사용한다면 시간초과없이 해결이 된다.