[프로그래머스] 부대복귀

문제

부대복귀

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

 

 

예시 코드

class Queue {
  constructor() {
    this.inbox = [];
    this.outbox = [];
  }

  enqueue(data) {
    this.inbox.push(data);
  }

  dequeue() {
    if (!this.outbox.length) {
      while (this.inbox.length) {
        this.outbox.push(this.inbox.pop());
      }
    }
    return this.outbox.pop();
  }

  size() {
    return this.inbox.length + this.outbox.length;
  }

  isEmpty() {
    return this.size() === 0;
  }
}

function solution(n, roads, sources, destination) {
  const answer = [];
  const graph = new Map();
  for (const [a, b] of roads) {
    if (!graph.has(a)) graph.set(a, []);
    if (!graph.has(b)) graph.set(b, []);
    graph.get(a).push(b);
    graph.get(b).push(a);
  }
  const distances = Array(n + 1).fill(Infinity);
  bfs();

  for (const source of sources) {
    const distance = distances[source];
    answer.push(distance === Infinity ? -1 : distance);
  }

  return answer;

  function bfs() {
    distances[destination] = 0;
    const queue = new Queue();
    queue.enqueue([destination, 0]);

    while (!queue.isEmpty()) {
      const [current, dist] = queue.dequeue();
      const adjacentNodes = graph.get(current) || [];

      for (const next of adjacentNodes) {
        if (distances[next] <= dist + 1) continue;
        distances[next] = dist + 1;
        queue.enqueue([next, dist + 1]);
      }
    }
  }
}

 

풀이

각 부대원이 부대로 복귀하기까지 걸리는 최단 시간을 구하는 문제입니다.

그래프 탐색을 통해 해결할 수 있고, 최단 시간을 구하는 것이므로 BFS를 사용했습니다.

 

먼저 각 노드(지역)별로 인접한 노드의 정보를 담은 그래프를 구성합니다.

각 노드까지의 거리를 담은 distances 배열의 각 원소를 Infinity로, 목적지를 0으로 초기화해서, 한번 갔던 곳은 재방문하지 않도록 합니다.

목적지에서 BFS를 수행해 각 지역까지 걸리는 시간을 구합니다.

도달할 수 없는 지역은 -1로 갱신합니다.