Lv 3. 부대복귀

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

프로그래머스

 

 

 

이 문제는 특정 목적지에서 여러 출발지까지의 최소 이동 거리를 구하는 문제다.
주어진 그래프는 양방향 도로로 연결되어 있으며,
BFS를 사용해 목적지로부터 각 노드까지의 거리를 계산한다.

먼저 solution 메서드는 입력으로 주어진 그래프 정보를 graph 리스트 배열로 초기화하고,
각 노드의 거리를 저장할 cost 배열을 -1로 초기화하여 방문 여부와 거리를 동시에 관리한다.
그런 다음, 모든 도로 정보를 읽어 graph에 양방향으로 저장한다.

핵심은 bfs 메서드로, 목적지에서 출발해 각 노드로의 최단 거리를 구한다.
큐를 사용해 BFS를 구현하며, 큐에서 노드를 하나씩 꺼내 해당 노드와 연결된 노드를 탐색한다.
아직 방문하지 않은 노드(cost[num] == -1)는 큐에 추가하고,
현재 노드까지의 거리에서 1을 더한 값을 해당 노드의 거리로 설정한다. 이렇게 하면 최단 거리가 자동으로 계산된다.

최종적으로 각 출발지 노드가 저장된 sources 배열을 순회하며, cost 배열에서 각 노드의 거리를 가져와 결과 배열에 저장한다.
만약 어떤 출발지가 목적지에 도달할 수 없는 경우, 그 값은 초기값인 -1로 유지된다.
마지막으로 결과 배열을 반환해 각 출발지에서 목적지까지의 최소 거리를 반환한다.

 

 

 

import java.util.*;

class Solution {
    
    List<Integer>[] graph;
    int[] cost;
    
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        graph = new ArrayList[n+1];
        for(int i = 0 ; i <= n ; i++) graph[i] = new ArrayList<>();
        
        for(int[] road : roads){
            graph[road[0]].add(road[1]);
            graph[road[1]].add(road[0]);
        }
        
        cost = new int[n+1];
        Arrays.fill(cost,-1);
        
        bfs(destination);
        
        return Arrays.stream(sources)
            .map(idx->cost[idx])
            .toArray();
    }
    private void bfs(int start){
        Queue<Integer> q = new ArrayDeque<>();
        q.add(start);
        cost[start] = 0;
        
        while(!q.isEmpty()){
            
            int now = q.poll();
            int len = graph[now].size();
            
            for(int i = 0 ; i < len ; i++){
                int num = graph[now].get(i);
                if(cost[num] == -1){
                    q.add(num);
                    cost[num] = cost[now] + 1;
                }
            }
        }
    }
        
    
}