[lv3] 부대 복귀

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

 

일단 희소그래프 이므로 인접리스트로 구현했다.

 

풀이 1 - BFS + cost 배열(dp)

 

BFS를 사용하므로, destination에 도착하면 항상 최단 거리임이 보장된다.

큐가 비어있는데도 destination에 도착하지 못한다면 -1을 넣는다.

 

단, BFS만 사용하면 시간초과가 발생하므로

노드 at에서 destination까지 가는 비용을 적은 cost[at]이 이미 존재한다면 사용하고 탐색을 마친다.

 

import java.util.*;

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

        List<List<Integer>> adj = new ArrayList<>();
        int R = roads.length;

        int[] cost = new int[n+1];
        int MAX = n+1;

        Arrays.fill(cost, MAX);

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

        for(int i=0; i<R; i++) {
            int from = roads[i][0];
            int to = roads[i][1];

            adj.get(from).add(to);
            adj.get(to).add(from);
        }

        int S = sources.length;
        List<Integer> ans = new ArrayList<>();

        for(int i=0; i<S; i++) {

            Queue<int[]> q = new ArrayDeque<>();
            boolean[] vst = new boolean[n+1];
            boolean find = false;

            q.offer(new int[]{sources[i], 0});
            vst[sources[i]] = true;

            while(!q.isEmpty()) {
                int[] info = q.poll();

                int at = info[0];
                int dep = info[1];

                if(at == destination) {
                    ans.add(dep);
                    cost[at] = dep;
                    find = true;
                    break;
                }

                if(cost[at] != MAX) {
                    ans.add(dep);
                    find = true;
                    break;
                }

                List<Integer> list = adj.get(at);
                int L = list.size();

                for(int j=0; j<L; j++) {
                    int next = list.get(j);

                    if(!vst[next]) {
                        vst[next] = true;
                        q.offer(new int[]{next, dep+1});
                    }
                }
            }

            if(!find) ans.add(-1);
        }

        int[] answer = new int[ans.size()];
        for(int i=0; i<ans.size(); i++) answer[i] = ans.get(i);

        return answer;
    }
}

 

 

풀이 2 - 한 번의 BFS 탐색

 

조금만 시각을 바꿔보면, n번째 노드에서 destination으로 도착하는 비용을 sources.length번 구하는 대신,

destination에서 모든 노드로 가는 비용을 한 번만 구해놓으면 된다.

 

import java.util.*;

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

        List<List<Integer>> adj = new ArrayList<>();
        int R = roads.length;

        int[] cost = new int[n+1];
        int MAX = n+1;

        Arrays.fill(cost, MAX);

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

        for(int i=0; i<R; i++) {
            int from = roads[i][0];
            int to = roads[i][1];

            adj.get(from).add(to);
            adj.get(to).add(from);
        }

        Queue<int[]> q = new ArrayDeque<>();
        boolean[] vst = new boolean[n+1];

        q.offer(new int[]{destination, 0});
        vst[destination] = true;

        while(!q.isEmpty()) {
            int[] info = q.poll();

            int at = info[0];
            int dep = info[1];

            cost[at] = dep;

            List<Integer> list = adj.get(at);
            int L = list.size();

            for(int j=0; j<L; j++) {
                int next = list.get(j);

                if(!vst[next]) {
                    vst[next] = true;
                    q.offer(new int[]{next, dep+1});
                }
            }

        }

        int S = sources.length;
        int[] ans = new int[S];

        for(int i=0; i<S; i++) {
            int val = cost[sources[i]];
            ans[i] = val == MAX ? -1 : val;
        }

        return ans;
    }
}