프로그래머스 - Lv.3 부대 복귀 (BFS) JS

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

해당 문제는 총 지역 수, 왕복 가능한 두 지역을 원소로 하는 배열, 각 부대원들이 위치한 지역, 목적지가 주어질 때, 각 부대원들이 부대로 도착할 수 있는 최소시간을 출력해야 하는 문제다.

 

문제 풀이 방식

출발지에서 목적지까지 도착이 가능한지 확인하는 방법도 있겠으나, 반대로 목적지에서부터 출발지에 도착할 수 있는지 기록하는 것이 메모리나 시간 측면에서 유리할 것이라 판단하여 이를 바탕으로 로직을 작성하였다.

 

function solution(n, roads, sources, destination) {
  const distances = Array.from({ length: n + 1 }, () => -1);
  const edges = Array.from({ length: n + 1 }, () => []);

  roads.forEach(([from, to]) => {
    edges[from].push(to);
    edges[to].push(from);
  });

  distances[destination] = 0;
  const queue = [[0, destination]];
  let queueIdx = 0;

  while (queueIdx < queue.length) {
    const [dist, cnt] = queue[queueIdx++];

    edges[cnt].forEach((next) => {
      if (distances[next] === -1) {
        queue.push([dist + 1, next]);
        distances[next] = dist + 1;
      }
    });
  }

  return sources.map((el) => distances[el]);
}