글 읽기 - Node.js 11724번 BFS 시간초과

luciferkala 4년 전 0

dfs로 구현을 했을 때는 통과가 되는데, BFS로 구현을 하니 시간초과가 나네요ㅠㅠㅠ

스택을 큐로 바꾼거 말고 다른것이 없는데 그것이 차이가 큰가요???

해결법을 알려주시면 감사하겠습니다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

const input = [];
const graph = [];
let check = [];
let answer = 0;
const bfs = node => {
  const q = [];
  if (check[node] === false) answer++;
  q.push(node);
  while (q.length > 0) {
    let next = q.shift();
    if (check[next] === false) {
      check[next] = true;
      q.push(...graph[next]);
    }
  }
};
rl.on("line", line => {
  input.push(line);
}).on("close", () => {
  const [vertax, edge] = input
    .shift()
    .split(" ")
    .map(element => parseInt(element));
  for (let i = 0; i <= vertax; i++) graph[i] = [];
  for (let l of input) {
    let [v1, v2] = l.split(" ").map(element => parseInt(element));
    graph[v1].push(v2);
    graph[v2].push(v1);
  }
  check = Array(vertax + 1).fill(false);
  for (let a = 1; a <= vertax; a++) if (check[a] === false) bfs(a);
  console.log(answer);
  process.exit();
});

domece 4년 전 1

shift는 매우 느립니다. 배열의 끝이 아닌 임의의 위치에서 항목을 삭제하는 것은 큰 대가를 치뤄야 하기 때문입니다.

luciferkala 4년 전 0

흠...그러면 저것을 BFS로 구현할 때 shift() 연산을 하지 않는다면 어떤 방법이 있을지 궁금합니다

domece 4년 전 0

항목을 삭제하는 대신 head와 tail 인덱스를 저장하면 됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Node.js 11724번 BFS 시간초과

luciferkala 4년 전 0

domece 4년 전 1

luciferkala 4년 전 0

domece 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말