[Algorithm] 부대복귀

📋 문제

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.

강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 담은 배열을 return하는 solution 함수를 완성해주세요. 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다.

 

제한 사항

• 3 ≤ n ≤ 100,000
  • 각 지역은 정수 1부터 n까지의 번호로 구분됩니다.
• 2 ≤ roads의 길이 ≤ 500,000
  • roads의 원소의 길이 = 2
  • roads의 원소는 [a, b] 형태로 두 지역 a, b가 서로 왕복할 수 있음을 의미합니다.(1 ≤ a, b ≤ n, a ≠ b)
  • 동일한 정보가 중복해서 주어지지 않습니다.
    • 동일한 [a, b]가 중복해서 주어지지 않습니다.
    • [a, b]가 있다면 [b, a]는 주어지지 않습니다.
• 1 ≤ sources의 길이 ≤ 500
  • 1 ≤ sources[i] ≤ n
• 1 ≤ destination ≤ n

 

입출력 예

3	[[1, 2], [2, 3]]	[2, 3]	1	[1, 2]
5	[[1, 2], [1, 4], [2, 4], [2, 5], [4, 5]]	[1, 3, 5]	5	[2, -1, 0]

 

✏️ 풀이

문제를 읽고 길을 그래프화 시켜서 BFS를 돌리면 될 것이라고 생각했다. 그래프는 객체 내 배열로 구성했고 매개변수인 roads는 양방향이기 때문에 양쪽에 넣어줬다. 최단거리이기 때문에 방문한 지점을 다시 방문하다보면 의도치않은 먼 길이 나올 것이고 시간초과로 이어질 수 있어 check 배열을 활용했고 answer에는 sources 순서대로 들어가야 하기 때문에 별도의 코드가 필요하다고 판단했다. 따라서 100,000의 길이인 배열에 최단거리를 표시해두고 sources를 순회하면서 answer에 넣어줬다.

 

⌨️ 코드

function solution(n, roads, sources, destination) {
  var answer = [];

  const graph = {};

  for (const road of roads) {
    const [start, end] = road;
    if (graph[start]) graph[start].push(end);
    else graph[start] = [end];
    if (graph[end]) graph[end].push(start);
    else graph[end] = [start];
  }

  const queue = [destination];
  const sourcesArr = new Array(100000).fill(-1);
  const check = new Array(100000).fill(0);
  let dist = 1;

  sourcesArr[destination] = 0;
  check[destination] = 1;

  while (queue.length) {
    const len = queue.length;
    for (let i = 0; i < len; i++) {
      const area = queue.shift();
      if (!graph[area]) continue;

      for (const nextArea of graph[area]) {
        if (check[nextArea]) continue;
        sourcesArr[nextArea] = dist;
        check[nextArea] = 1;
        queue.push(nextArea);
      }
    }
    dist++;
  }

  for (const source of sources) {
    answer.push(sourcesArr[source]);
  }

  return answer;
}