[백준] - 18352 특정 거리의 도시 찾기 (node.js / BFS)

문제링크

풀이

BFS로 풀었다. shift()를 사용하면 시간초과가 나서.. 현재 first를 가리키는 index를 통해 큐의 FIFO를 구현했다.

코드

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

const [n, m, k, x] = input[0].split(" ").map(Number);

let graph = Array.from(new Array(n + 1), () => new Array());

for (let i = 1; i <= m; i++) {
  const [p, q] = input[i].split(" ").map(Number);
  graph[p].push(q);
}

let result = [];
// bfs
let visited = new Array(n + 1).fill(0);
let q = [[x, 0]];
let index = 0;
while (index < q.length) { // q.length === index >> 큐가 비었다
  let [node, len] = q[index++]; // shift하면 시간초과!!
  visited[node] = 1;
  if (len === k) {
    result.push(node);
  }
  for (const no of graph[node]) {
    if (visited[no]) continue;
    q.push([no, len + 1]);
    visited[no] = 1;
  }
}

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

다른 풀이를 찾아보니 visited에 거리를 저장하는 방식으로 하시는 분도 계셨다. 신기방기.