프로그래머스 LV3 부대복귀

 

https://school.programmers.co.kr/learn/courses/30/lessons/132266

다익스트라 알고리즘을 활용해야 했다.

다 까먹은 다익스트라 알고리즘을 하나하나 다시 만드는데 있어서 시간이 오래 걸리진 않았다.

블로그 포스팅한 이유는 Comparable, Comparator를 활용한 우선순위큐 만드는 것을 잊지않을려고 올린다.

 

 

import java.util.*;
class Solution {
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int [sources.length];
        ArrayList<Integer> [] arr = new ArrayList[n+1];
        PriorityQueue<Point> pq = new PriorityQueue<>();
        int [] distance = new int[n+1];

        for (int i = 0 ; i < arr.length; i++) {
            arr[i] = new ArrayList <>();
            distance[i] = Integer.MAX_VALUE;
        }
        
        for (int [] road : roads) {
            int start = road[0];
            int end = road[1];
            arr[start].add(end);
            arr[end].add(start);
        }
        
        distance[destination] = 0;
        pq.add(new Point(0,destination));
        
        while (!pq.isEmpty()) {
            Point now = pq.poll();
            if (now.distance > distance[now.node]) continue;
            for (int dest : arr[now.node]) {
                int sumDistance = now.distance + 1;
                if (sumDistance < distance[dest]) {
                    distance[dest] = sumDistance;
                    pq.add(new Point(sumDistance,dest));
                }
            }
        }
       
        for (int i = 0 ; i < sources.length ;i++) {
            answer[i] = distance[sources[i]] == Integer.MAX_VALUE ? -1 : distance[sources[i]];
        }
        
        return answer;
    }
    public static class Point implements Comparable <Point> {
        int distance;
        int node;
        Point (int distance,int node) {
            this.distance = distance;
            this.node = node;
        }
        
        public int compareTo (Point a) {
            return this.distance - a.distance;
        }
    }
}