부대복귀

문제를 봤을때 워셜-플로이드 알고리즘과 다익스트라 알고리즘이 생각이 났다.
또한 범위가 10만이기 때문에 그래프를 모두 표현하는 워셜-플로이드보다는 시간복잡도가 O(VlogV + ElogV)인 다익스트라 알고리즘이 효과적일것이라고 생각했다.

코드

import java.util.*;
class Solution {
    int[] dist;
    int MAX= Integer.MAX_VALUE-1000000;
    ArrayList<ArrayList<Integer>> list;
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        list = new ArrayList<>();
        dist = new int[n+1];
        int[] answer= new int[sources.length];
        Arrays.fill(dist,MAX);
             
        for(int i=0;i<n+1;i++){
            list.add(new ArrayList<>());
        }
         for(int[] road: roads){
            list.get(road[0]).add(road[1]); 
            list.get(road[1]).add(road[0]);
        }
        dijkstra(destination);
        for(int i=0;i<answer.length;i++){
            answer[i]= (dist[sources[i]]!=MAX)?dist[sources[i]]:-1;
        }
        return answer;
    }
    public void dijkstra(int destination){
//        PriorityQueue<Integer> q = new PriorityQueue<Integer>((o1, o2) -> Integer.compare(o1, o2));
        Queue<Integer> q = new LinkedList<>();
        q.offer(destination);		
		dist[destination] = 0;
        while (!q.isEmpty()) {
			int cur = q.poll();
			
			

			for (int i = 0; i < list.get(cur).size(); i++) {
				int nCur = list.get(cur).get(i);
				
				if (dist[nCur] > dist[cur]+1) {
					dist[nCur] = dist[cur]+1;				
					q.offer(nCur);
				}
			}
		}

        
    }
}//우선순위 다익스트라

문제를 풀고나서 우선순위 큐를 사용했었는데 너무 오랜시간이 걸리는것을 확인했다.
무슨 문제인지 생각해봤는데 사실 가중치가 무조건 1인 그래프라 우선순위큐를 통해서 값을 찾으면 빠져나오는것이 아닌 모든 큐를 끝내야 나올수있는 문제였다.
따라서 한번 큐를 정렬할때마다 걸리는 시간이 너무 오래걸린다는것을 확인할수있었다.