부대복귀

문제 정보

• 프로그래머스 Lv.3
• 최단경로, BFS
• 문제 링크

풀이

그래프에서의 최단 경로를 구하는 문제다.

모든 가중치가 동일하기 때문에, BFS를 사용하면 된다.

코드

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[] road : roads) {
            graph.get(road[0]).add(road[1]);
            graph.get(road[1]).add(road[0]);
        }
        
        int[] time = bfs(n, destination, graph);
        
        int[] answer = new int[sources.length];
        for (int i = 0; i < sources.length; i++) {
            int t = time[sources[i]];
            answer[i] = t;
        }
        
        return answer;
    }
    
    private int[] bfs(int n, int start, List<List<Integer>> graph) {
        int[] cost = new int[n + 1];
        Arrays.fill(cost, -1);
        
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);
        cost[start] = 0;
        
        while (!q.isEmpty()) {
            int cur = q.poll();
            
            for (int next : graph.get(cur)) {
                if (cost[next] != -1)
                    continue;
                
                cost[next] = cost[cur] + 1;
                q.offer(next);
            }
        }
        
        return cost;
    }
}

관련 노트

• BFS