백준25516 - 거리가 k이하인 트리 노드 (BFS) node.js

https://www.acmicpc.net/problem/25516

자바스크립트 정답자가 2명 뿐이라 포스팅하게 된 문제. BFS 알고리즘에 대해 이해하고 있다면 어렵지 않다.

 

문제 해결 방식

먼저 문제에서 제시된 트리 구조를 구현한 뒤, BFS 알고리즘을 구현했다. 이때, 문제에서는 '수확할 수 있는 사과까지의 거리'가 주어져 있으므로, 큐(대기열)에 원소를 삽입 시 루트 노드까지의 거리를 담아 삽입하는 방식으로 구현했다.

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const arr = data.map((el) => el.split(" ").map(Number));
  const [n, k] = arr.shift(),
    apples = arr.pop();

  const graph = Array.from({ length: n }, () => []);

  arr.forEach(([a, b]) => {
    graph[a].push(b);
    graph[b].push(a);
  });

  const visited = Array.from({ length: n }, () => false);
  const queue = [[0, 0]];
  let result = 0;
  let queueIdx = 0;

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

    if (visited[node] || cnt > k) break;
    visited[node] = true;
    if (apples[node]) result++;

    graph[node].forEach((next) => {
      if (!visited[next]) queue.push([next, cnt + 1]);
    });
  }

  console.log(result);
}

solution(input);