특정 거리의 도시 찾기

• https://www.acmicpc.net/problem/18352

오늘의 학습 키워드

BFS

• 정점과 같은 레벨에 있는 노드(형제 노드)를 먼저 탐색하는 방식
• 큐 자료구조를 사용하여 인접한 정점들의 리스트를 관리한다

문제 해결 방법

• 단방향 그래프임을 고려한다
• BFS를 활용해 문제를 해결한다
  1. 시작 노드를 큐에 넣고 방문 처리한다
  2. 큐에서 원소를 꺼내어 방문하지 않은 인접 노드가 있는지 확인한다
     • 있다면, 방문하지 않은 인접 노드를 큐에 모두 삽입하고 방문 처리한다
  3. 2번 과정을 더 이상 반복할 수 없을 때까지 반복한다.
• 최단 거리가 K인 도시의 번호가 입력된 answer를 오름차순으로 출력하지만, 존재하지 않을 경우 -1을 출력한다

코드

// input
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");
const [N, M, K, X] = input.shift().split(" ").map(Number);
const roads = input.map((v) => v.split(" ").map(Number));
const distance = Array(N + 1).fill(0);
let answer = [];

// G (graph)
const G = Array.from(new Array(N + 1), () => []);
roads.map(([u, v]) => G[u].push(v));

// BFS
function bfs(start) {
  const queue = [start];
  distance[start] = 1;

  while (queue.length) {
    const cur = queue.shift();
    if (distance[cur] === K + 1) answer.push(cur);
    G[cur].forEach((next) => {
      if (!distance[next]) {
        queue.push(next);
        distance[next] = distance[cur] + 1;
      }
    });
  }
}
bfs(X);

answer = !answer.length ? -1 : answer.sort((a, b) => a - b).join("\n");
console.log(answer);

이번에는 Queue 클래스를 활용하지 않고, 단순 배열을 활용해서 구현해봤다