문제 - 부대복귀

문제 접근

1. 처음에는 dfs로 접근을 할려고하니까 재귀호출은 아직 어려워서 stackoverflow가 계속나서 포기를 했다.
2. 모든 start지점에서 destination 지점까지 bfs를 돌려 보니 최대가 100_000 * 100_000이라서 시간초과가 났다.
3. 미리 bfs를 이용하여 목적지에서 모든 지점에 대한 거리를 계산을 했다.
4. 다익스트라로도 모든 지점에 대한 비용을 계산할 수 있으므로 해당 알고리즘을 사용해도 되지만 아직 익숙치 않아서 사용을 못했다.

import java.util.*;

class Solution {
    ArrayList<Integer> lists[];
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int[sources.length];
        //이동할 수 있는 길 연결
        lists = new ArrayList[n+1];
        for(int i=0;i<=n;i++)
        {
            lists[i] = new ArrayList<>();
        }
        
        
        for(int i =0;i<roads.length;i++)
        {
            lists[roads[i][0]].add(roads[i][1]);
            lists[roads[i][1]].add(roads[i][0]);
        }
        
        int cost[] = new int[n+1];//해당 경로에 필요한 비용 계산
        Arrays.fill(cost,-1); //경로가 없는 경우 -1로 설정
        bfs(destination,cost);
        
        for(int i = 0;i< sources.length;i++ )
        {
            answer[i] = cost[sources[i]];
        }
        
        return answer;
    }
    
    public void bfs(int start,int []cost)
    {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        cost[start] = 0;
        
        while(!q.isEmpty())
        {
            int cnt = q.poll();
            int len = lists[cnt].size();
            
            for(int i=0;i<len;i++ )
            {
                int next = lists[cnt].get(i);
                if(cost[next] == -1) 
                {
                    q.offer(next);
                    cost[next] = cost[cnt] + 1;
                }
            }
        }
        
    }
}