프로그래머스 - 부대복귀(Java)

다익스트라(dijkstra) 문제입니다.

 

연결 정보가 주어지고, 여러 출발지에서 하나의 목적지 까지로 가는 가중치를 구하는 문제입니다.

무방향 그래프이기 때문에 이를 반대로 생각하면, 하나의 목적지에서 여러 출발지까지 가는 가중치를 구하는 문제로 해석할 수 있습니다.

즉, 하나의 시점에서 다른 노드들로 가는 최소 가중치를 구하는 문제이므로 다익스트라인 것을 알 수 있습니다.

 

다익스트라 시간 복잡도는 O(VlogV + ElogV)입니다.

log500,000의 값이 18.931568569324174이므로, 19로 계산하겠습니다.

500,000*19 + 100,000*19 = 11,400,000 입니다.

이정도면 허용범위 내라고 할 수 있기 때문에, 다익스트라 시간복잡도로 해결할 수 있습니다.

 

[구현 코드]

import java.util.*;

class Solution {
    private static List<List<Integer>> graph;
    private static int[] dis;
    private static final int MAX = 1_000_000_000;

    public static int[] solution(int n, int[][] roads, int[] sources, int destination) {

        graph = new ArrayList<>();
        for(int i=0; i<n+1; i++) graph.add(new ArrayList<>());

        for (int[] road : roads) {
            int s = road[0];
            int e = road[1];

            graph.get(s).add(e);
            graph.get(e).add(s);
        }

        dis = new int[n+1];
        Arrays.fill(dis, MAX);
        dijkstra(destination);

        int[] ans = new int[sources.length];
        for (int i = 0; i < sources.length; i++) {
            ans[i] = (dis[sources[i]] < MAX) ? dis[sources[i]] : -1;
        }
        return ans;
    }

    private static void dijkstra(int destination) {
        Queue<Integer> qu = new LinkedList<>();
        qu.add(destination);
        dis[destination] = 0;

        while (!qu.isEmpty()){
            int cn = qu.poll();

            for(int i=0; i<graph.get(cn).size(); i++){
                int nn = graph.get(cn).get(i);
                if(dis[nn] > dis[cn]+1){
                    dis[nn] = dis[cn]+1;
                    qu.add(nn);
                }
            }
        }
    }
}