[프로그래머스] 부대복귀

문제 설명

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

문제 풀이

• dijkstra로 풀어도 되고, 간선 가중치가 모두 1이므로 BFS로 풀어도 무방하다.
• 문제의 핵심은 각 source로 부터 destination까지 최소거리를 구하는 것이 아닌,
  destination으로 부터 출발하여 각 노드까지의 최소거리를 구하는 것이다. (시간 초과 피하기)
• 아래 소스 참조

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int N, D;
    public List<List<Integer>> edge;
    public int[] min;

    public class Point {
        int n, c;
        public Point (int n, int c) {
            this.n = n;
            this.c = c;
        }
    }

    public int dijkstra() {
        Queue<Point> q = new ArrayDeque<>();
        min[D] = 0;
        q.add(new Point(D, 0));
        while(!q.isEmpty()) {
            Point cur = q.poll();
            for (int i = 0; i < edge.get(cur.n).size(); i++) {
                int nextN = edge.get(cur.n).get(i);
                if (min[nextN] != -1) continue;
                min[nextN] = cur.c + 1;
                q.add(new Point(nextN, cur.c + 1));
            }
        }
        return -1;
    }

    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        N = n;
        D = destination;

        edge = new ArrayList<>();
        for (int i = 0; i <= N; i++)
            edge.add(new ArrayList<>());

        for (int i = 0; i < roads.length; i++) {
            int from = roads[i][0];
            int to = roads[i][1];
            edge.get(from).add(to);
            edge.get(to).add(from);
        }
        //결과 계산
        min = new int[N + 1];
        Arrays.fill(min, -1);
        dijkstra();
        int[] result = new int[sources.length];
        for (int i = 0; i < sources.length; i++)
            result[i] = min[sources[i]];
        return result;
    }
}