[Lv.3] 부대복귀

import java.util.*;
class Solution {
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int[sources.length];
        //만약 시간초과만 나면 플루이드 와샬로
        Map<Integer,List<Integer>> roadMap=new HashMap<>();
        for(int i=1;i<=n;i++){
            List<Integer> list=new ArrayList<>();
            roadMap.put(i,list);
        }
        for(int[] road: roads){
            roadMap.get(road[0]).add(road[1]);
            roadMap.get(road[1]).add(road[0]);
        }
        
        //reverse
        PriorityQueue<Node> pq=new PriorityQueue<>((o1,o2)->o1.cost-o2.cost);
        pq.add(new Node(destination,0));
        boolean[] visited=new boolean[n+1];
        //dest 부터 i까지의 최소 거리
        int[] distance=new int[n+1];
        for(int i=1;i<=n;i++)
            distance[i]=Integer.MAX_VALUE;
        distance[destination]=0;
        
        while(!pq.isEmpty()){
            Node node=pq.poll();
            visited[node.n]=true;
            List<Integer> targetList=roadMap.get(node.n);
            for(int i=0;i<targetList.size();i++){
                int idx=targetList.get(i);
                if(visited[idx])
                    continue;
                if(distance[idx]>distance[node.n]+1){
                    distance[idx]=distance[node.n]+1;
                    pq.add(new Node(idx,distance[idx]));
                }
            }
        }
        
        
        
        for(int i=0; i<sources.length; i++){
            answer[i]=(distance[sources[i]]!=Integer.MAX_VALUE)? distance[sources[i]]:-1;
        }
        return answer;
    }
    class Node{
        int n;
        int cost;
        public Node(int n, int cost){
            this.n=n;
            this.cost=cost;
        }
    }
}

---

다익스트라로 쉽게 풀 수 있는 문제다.

다만, 출발지를 sources가 아닌 destination으로 설정하고 destination에서 다른 노드들로의 최소 거리를 다익스트라로 구하게 되면 문제의 조건을 쉽게 만족할 수 있다.