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

문제 설명

강철부대원이 각 지역에서 본부로 복귀하는 데 필요한 최단시간을 구합니다. 복귀가 불가능하면 -1을 반환합니다.

---

제한 사항

• 3 ≤ n ≤ 100,000
• 2 ≤ roads 길이 ≤ 500,000
• 모든 길의 이동 시간은 1

---

해결 방법

• 알고리즘: BFS (Breadth-First Search)

1. 그래프 생성: 지역 간 연결 정보로 인접 리스트 구성
2. BFS 탐색: 부대 본부에서 시작하여 각 지역까지의 최단 거리 계산
3. 결과 반환: 각 부대원이 위치한 지역의 복귀 시간 출력

---

시간 복잡도

• 그래프 생성: O(E)
• BFS 탐색: O(V+E)
• 총합: O(V+E), V는 지역 수, E는 길의 수

---

구현 코드

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  push(value) {
    const node = new Node(value);

    if (this.size === 0) {
      this.front = node;
      this.rear = node;
    } else {
      this.rear.next = node;
      this.rear = node;
    }

    ++this.size;
  }

  pop() {
    if (this.size === 0) {
      return null;
    }

    const value = this.front.value;
    this.front = this.front.next;
    --this.size;

    if (this.size === 0) {
      this.rear = null;
    }

    return value;
  }
}

function solution(n, roads, sources, destination) {
  let answer = [];
  let visit = new Array(n + 1).fill(-1);
  let dist = new Array(n + 1).fill(null).map(() => []);
  let q = new Queue();

  for ([a, b] of roads) {
    dist[a].push(b);
    dist[b].push(a);
  }

  q.push([destination, 0]);
  visit[destination] = 0;

  while (q.size > 0) {
    const [current, cost] = q.pop();

    for (const next of dist[current]) {
      if (visit[next] === -1) {
        visit[next] = cost + 1;
        q.push([next, cost + 1]);
      }
    }
  }

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

  return answer;
}