[코딩테스트]#8. 부대복귀(최단거리) 다익스트라 알고리즘

Description
강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.

강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 담은 배열을 return하는 solution 함수를 완성해주세요. 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다.

제한사항

• 3 ≤ n ≤ 100,000
  각 지역은 정수 1부터 n까지의 번호로 구분됩니다.
• 2 ≤ roads의 길이 ≤ 500,000
  roads의 원소의 길이 = 2
  roads의 원소는 [a, b] 형태로 두 지역 a, b가 서로 왕복할 수 있음을 의미합니다.(1 ≤ a, b ≤ n, a ≠ b)
  동일한 정보가 중복해서 주어지지 않습니다.
  동일한 [a, b]가 중복해서 주어지지 않습니다.
  [a, b]가 있다면 [b, a]는 주어지지 않습니다.
• 1 ≤ sources의 길이 ≤ 500
• 1 ≤ sources[i] ≤ n
• 1 ≤ destination ≤ n

입출력 예

 

입출력 예 설명
입출력 예 #1
지역 2는 지역 1과 길로 연결되어 있기 때문에, 지역 2에서 지역 1의 최단거리는 1입니다.
지역 3에서 지역 1로 이동할 수 있는 최단경로는 지역 3 → 지역 2 → 지역 1 순으로 이동하는 것이기 때문에, 지역 3에서 지역 1의 최단거리는 2입니다.
따라서 [1, 2]를 return합니다.

입출력 예 #2
지역 1에서 지역 5의 최단경로는 지역 1 → 지역 2 → 지역 5 또는 지역 1 → 지역 4 → 지역 5 순으로 이동하는 것이기 때문에, 최단거리는 2입니다.
지역 3에서 지역 5로 가는 경로가 없기 때문에, 지역 3에서 지역 5로 가는 최단거리는 -1입니다.
지역 5에서 지역 5는 이동할 필요가 없기 때문에, 최단거리는 0입니다.
따라서 [2, -1, 0]을 return합니다.

 

풀이 요약

이 문제는 각 부대원들의 위치에서 정해진 지역으로 최단거리로 이동하여 모이는 시간을 구해내는 문제로 최단거리를 구해야 하기 떄문에 다익스트라 알고리즘을 사용했다. start와 end를 통해 출발지역과 도착지역을 나타냈고 무방향 그래프이기 때문에 간선을 양방향 모두 넣어 두었다. 가중치는 모두 1로 동일하여 따로 넣진 않았다. visit 배열을 통해 해당 지역을 거쳤는지 확인 하였고 dist 배열을 통해 sources에 맞는 시간을 저장하여 answer에 매칭시켜 제출하였다.

 

다익스트라 알고리즘은 구현되어있는 소스코드를 수정하여 재 구현하였다.

 

풀이 소스코드

import java.util.*;

class Solution {
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visit;
    static int[] dist;

    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = {};
        dist = new int[n + 1];
        visit = new boolean[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] road : roads) {
            int start = road[0];
            int end = road[1];

            graph.get(start).add(end);
            graph.get(end).add(start);
        }

        for (int source : sources) {
            dijkstra(destination);
        }
        answer = new int[sources.length];
        int ansCnt = 0;
        for (int source : sources) {
            if (dist[source] == Integer.MAX_VALUE) {
                answer[ansCnt] = -1;
            } else {
                answer[ansCnt] = dist[source];
            }
            System.out.println("answer = " + answer[ansCnt]);
            ansCnt++;
        }
        return answer;
    }

    static void dijkstra(int start) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        q.add(start);
        dist[start] = 0;

        while (!q.isEmpty()) {

            int now = q.poll();
            for (int i = 0; i < graph.get(now).size(); i++) {
                int nn = graph.get(now).get(i);
                if (dist[nn] > dist[now] + 1) {
                    dist[nn] = dist[now] + 1;
                    q.add(nn);
                }
            }
        }
    }
}