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

     

목차

 

문제

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

프로그래머스

 

 

문제 구현 방향

처음에 bfs를 생각했었는데 각 시작점에 대해 bfs를 돌릴 경우 시간 복잡도가 날 것 같아 고민했던 문제이다.

목적지를 기준으로 모든 경로를 순회하고 시작점의 거리를 답에 추가해주면 되는 문제였다.

 

 

코드 구현

function solution(n, roads, sources, destination) {
    var answer = [];
    let board = Array.from({length: 100001}, ()=> []);
    for(let r of roads){
        let [str, end] = r;
        board[str].push(end);
        board[end].push(str);
    }
    let dp = Array(100001).fill(Infinity);
    let queue = [destination];

        dp[destination] =0;
        while(queue.length){
            let sft = queue.shift();
            for(let r of board[sft]){
                if(dp[r] === Infinity){
                    dp[r] = dp[sft] + 1;
                    queue.push(r);
                }
            }
        }
 
    for(let src of sources){
       answer.push(isFinite(dp[src]) ? dp[src] : -1);
        
    }
   
    return answer;
}