부대복귀

2025-10-13

#JAVA#프로그래머스

1분

문제 링크

문제 풀이 시간 : 15분

문제 요약

•
지도에는 1부터 n까지 번호가 붙은 지역이 존재하며, 각 지역은 양방향 도로(roads) 로 연결되어 있음

•
각 도로는 통과하는 데 걸리는 시간이 모두 1로 동일함

•
강철부대 본부가 위치한 지역 번호는 destination

•
여러 명의 부대원이 각각 다른 지역(sources)에서 복귀하려고 함

•
부대원은 최단 시간으로 destination으로 복귀하려 하지만,
일부 지역은 경로가 단절되어 복귀가 불가능할 수도 있음

•
복귀가 불가능한 경우에는 1을 반환해야 함

문제 풀이

이 문제는 예전에 스터디에서 진행했던 모의 코테에서 출제되었던 문제였다.

그때는 꽤나 어렵게 풀었고, 결국 못 풀었었다.

오늘 프로그래머스 추천 문제에서 이 문제가 나와서 이번에 다시 풀어보게 되었다.

처음에는 전처럼 꽤나 어려운 방식으로 접근을 하려고 했는데,

잠깐 생각해보니 그냥 destination에서 모든 가능한 경로를 미리 계산해두면 빠르게 풀 수 있는 아주 쉬운 문제였다..!

최종 코드

Java

import java.util.*;

class Solution {
    public List<Integer>[] arr;
    
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] dist = new int[n+1];
        
        arr = new ArrayList[n+1];
        for(int i=1;i<=n;i++)
            arr[i] = new ArrayList<>();
        
        //양방향 그래프 생성
        for(int i=0;i<roads.length;i++){
            arr[roads[i][0]].add(roads[i][1]);
            arr[roads[i][1]].add(roads[i][0]);
        }
        
        //거리 배열 -1 초기화
        Arrays.fill(dist,-1);
        dist[destination] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(destination);
        
        //bfs 탐색
        while(q.size()!=0){
            int now = q.poll();
            for(int next : arr[now]){
                if(dist[next]!=-1)
                    continue;
                q.add(next);
                dist[next] = dist[now]+1;
            }
        }
        
        //각 출발지에서 목적지까지 거리 가져오기
        int[] answer = new int[sources.length];
        for(int i=0;i<sources.length;i++){
            answer[i] = dist[sources[i]];
        }
        
        return answer;
    }
}