프로그래머스 - 부대 복귀(Javascript)

프로그래머스 - 부대 복귀

풀이과정

각 부대원들이 부대로 복귀하는 최단경로를 찾는 문제인데, bfs를 통해 각 부대원별로 목적지까지 최단 경로를 구하려다보니 시간초과가 발생했다.

아래는 시간 초과가 발생한 코드

function solution(n, roads, sources, destination) {
    const answer = [];
    const graph = [...Array(n+1)].map(()=>[]);
    for(const road of roads){
        const [a,b] = road;
        graph[a].push(b);
        graph[b].push(a);
    }

    // source에서부터 graph를 순회하여 destination에 도착하는 최단거리를 구하는 bfs 함수
    function bfs(start){
        if(start === destination) return 0;
        const visited = [...Array(n+1)].map(()=>false);
        const q = [[start, 0]];
        visited[start] = true;
        while(q.length){
            const [currentRegion, count] = q.shift();
            // area 도시에 연결된 도시들을 방문했는지 체크하고 이동
            for(const region of graph[currentRegion]){
                if(region === destination) return count + 1;
                if(!visited[region]){
                    q.push([region, count+1]);
                    visited[region] = true;
                }
            }
        }
        return -1;
    }
    for(const i of sources){
        answer.push(bfs(i))
    }
    return answer;
}

어떻게 효율성을 개선할 수 있을지 고민하다가 목적지는 하나이기에 결국 목적지로부터 부대원으로 가는 길을 찾으면 bfs를 한번만 실행하더라도 문제를 해결할 수 있음을 깨달았다.

정답코드

function solution(n, roads, sources, destination) {
    const answer = [];
    const graph = [...Array(n+1)].map(()=>[]);
    for(const road of roads){
        const [a,b] = road;
        graph[a].push(b);
        graph[b].push(a);
    }

    // source에서부터 graph를 순회하여 destination에 도착하는 최단거리를 구하는 bfs 함수
    function bfs(start){
        if(start === destination) return 0;
        const visited = [...Array(n+1)].map(()=>false);
        const q = [[start, 0]];
        visited[start] = true;
        while(q.length){
            const [currentRegion, count] = q.shift();
            // area 도시에 연결된 도시들을 방문했는지 체크하고 이동
            for(const region of graph[currentRegion]){
                if(region === destination) return count + 1;
                if(!visited[region]){
                    q.push([region, count+1]);
                    visited[region] = true;
                }
            }
        }
        return -1;
    }
    for(const i of sources){
        answer.push(bfs(i))
    }
    return answer;
}