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

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

프로그래머스

접근 방법

1. 임의의 노드에서 도착지까지의 최단거리를 구하면되므로 BFS를 떠올렸다.
2. 도착지를 기준으로 n개의 노드를 distMap에 기록하며 거리를 계산하고 출력했다.

코드

import java.util.*;
class Solution {
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        List<List<Integer>> graph = new ArrayList<>();
        for(int i = 0 ; i <= n ; i++)graph.add(new ArrayList<>());
        
        for(int[] r: roads){
            int s = r[0];
            int e = r[1];
            
            graph.get(s).add(e);
            graph.get(e).add(s);
        }
        
        int[] distMap = new int[n+1];
        boolean[] vis = new boolean[n+1];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{destination,0});
        vis[destination] = true;
        
        while(!q.isEmpty()){
            int[] cur = q.poll();
            distMap[cur[0]] = cur[1];
            
            for(int next: graph.get(cur[0])){
                if(vis[next]) continue;
                q.offer(new int[]{next,cur[1]+1});
                vis[next] = true;
            }
        }
        
        
        int[] answer = new int[sources.length];
        for(int i = 0 ; i< sources.length ; i++){
            int dist = distMap[sources[i]];
            answer[i] = dist == 0 && sources[i] != destination? -1: dist;
        }
        return answer;
    }
}