프로그래머스 부대복귀 javascript

🖇️프로그래머스

풀이

​

정점 사이의 간선의 길이가 1로 정해져 있다. ​

이게 유동적이면 bfs로 해결할 수 없지만 (다익스트라, 플로이드 와샬 등 사용으로 해결)

​ 1로 일정하기에 bfs로 풀었다.

1. graph에 경로들을 담아두고 ​
2. bfs 돌리면서 visited의 최소 시간으로 방문한 값을 저장하다. ​
3. map 돌리면서 출력 ​

코드

function solution(n, roads, sources, destination) {
    const graph = new Array(n+1).fill(null).map(_=>[]);
    for(let [a,b] of roads){
        graph[a].push(b);
        graph[b].push(a);
    }
    const visited = new Array(n+1).fill(Infinity);
    const bfs = (destination) =>{
        const q = [destination];
        visited[destination] = 0;
        while(q.length > 0){
            const idx = q.shift();
            for(let newIdx of graph[idx]){
                if(visited[idx]+1 < visited[newIdx]){
                    visited[newIdx] = visited[idx]+1;
                    q.push(newIdx);
                }
            }
        }
    }
    bfs(destination);
​
    return sources.map(v=>{
        if(visited[v] === Infinity) return -1;
        else return visited[v];
    });
}