프로그래머스 - 부대복귀

        길이 50만개다. 다익스트라 한번 돌리는데, 1백만이다
        500개의 sourece가 있으면 500만이다. 
         고로 다익스트라로 풀어도 풀린다.
         풀릴줄 알았따. 근데 안풀린다 ㅎㅎ..

 

다시!!

         

목적지는 정해져 있다.
         목적지에서 전 범위를 돌리면 ?

풀린다.

 

알고 푼다기 보단... 대충 때려맞춰서 운 좋게 풀었다.

 

다익스트라는 뭔가 ? 한 점에서 다른 점까지의 최단 거리를 구하는 것이다.

목적지점에서 출발지로 다익스트라를 돌려서 풀었는데, 운이 좋았던 거 같다.

 

import java.util.*;
import java.io.*;

class info implements Comparable<info>{
    
    int idx,value;
    
    public info(int idx, int value){
        this.idx = idx;
        this.value = value;
    }
    
    @Override
    public int compareTo(info o){
        return this.value - o.value;
    }
    
}

class Solution {
    static List<Integer> list[];
    static int [] dist;
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        //길이 50만개다. 다익스트라 한번 돌리는데, 1백만이다
        //500개의 sourece가 있으면 500만이다. 
        // 고로 다익스트라로 풀어도 풀린다.
        // 그럴줄 알았따. 근데 안풀린다 ㅎㅎ..
        // 목적지는 정해져 있다.
        // 목적지에서 전 범위를 돌리면 ?
        int[] answer = new int[sources.length];
        dist = new int[n+1];
        
        list = new List[n+1];
        for(int i =1; i<=n; i++){
            list[i]= new ArrayList<>();
        }
        

        for(int i =0; i<roads.length; i++){
            int from = roads[i][0];
            int to = roads[i][1];
            list[from].add(to);
            list[to].add(from);
        }
        
        dijkstra(destination, n);
        
        for(int i =0; i<sources.length; i++){
            answer[i]=dist[sources[i]];
            if(answer[i]==100001){
                answer[i]=-1;
            }
        }
        
        return answer;
    }
    
    private static void dijkstra(int destination, int n){
        
        Arrays.fill(dist, 100001);
        PriorityQueue<info>pq = new PriorityQueue<>();
        dist[destination]=0;
        pq.add(new info(destination,0));
        
        while(!pq.isEmpty()){
            info cur = pq.poll();
            int curIdx = cur.idx;
            int curCost = cur.value;
            
            if(dist[curIdx]<curCost)continue;
            
            for(int i =0; i<list[curIdx].size(); i++){
                int nextIdx = list[curIdx].get(i);
                int nextCost = curCost+1;
                
                if(nextCost<dist[nextIdx]){
                    dist[nextIdx]=nextCost;
                    pq.add(new info(nextIdx,nextCost));
                }
            }
        }
    }
}