[JS] 부대복귀

문제

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

 

풀이

해당 문제는 BFS를 이용한 다익스트라다 문제이며, 처음 문제를 풀때는 주어지는 sources별로 마지막 도착지인 destination까지의 거리를 측정했었다.

 

하지만 이렇게 풀게 되면 시간 초과가 발생한다.

function solution(n, roads, sources, destination) {
    const answer = [];
    const road = Array.from({length: n + 1}, () => []);
    const level = Array.from({length: n + 1}, () => Infinity);
    
    for(let i = 0; i < sources.length; i++){
        const visited = Array.from({length: n + 1}, () => false);
        let level = Array.from({length: n + 1}, () => -1);
        const que = [sources[i]];
        level[sources[i]] = 0;
        visited[sources[i]] = true;
        
        while(que.length > 0){
            const man = que.shift();
            for(let temp of roads){
                if(temp[0] === man && !visited[temp[1]]){
                    level[temp[1]] = level[man] + 1;
                    visited[temp[1]] = true;
                    que.push(temp[1]);
                }
                else if(temp[1] === man && !visited[temp[0]]){
                    level[temp[0]] = level[man] + 1;
                    visited[temp[0]] = true;
                    que.push(temp[0]);
                }
            }
        }
        answer.push(level[destination]);
    }
    return answer;
}

 

생각의 반전이 필요하다. 목적지를 기준으로 각 요원의 위치까지의 최단 거리를 구하면 된다.

 

코드

function solution(n, roads, sources, destination) {
  const answer = [];
  const road = Array.from({ length: n + 1 }, () => []);
  const level = Array.from({ length: n + 1 }, () => Infinity);
  const que = [destination];
  roads.forEach(([st, ed], i) => {
    road[st].push(ed);
    road[ed].push(st);
  })
    
  level[destination] = 0;
    
  while (que.length > 0) {
    const cur = que.shift();
    for (let i = 0; i < road[cur].length; i++) {
      if (level[cur] + 1 < level[road[cur][i]]) {
        level[road[cur][i]] = level[cur] + 1;
        que.push(road[cur][i]);
      }
    }
  }
    
  sources.forEach(e => {
    answer.push(level[e] === Infinity ? -1 : level[e]);
  })
  return answer;
}