[백준][dfs / bfs] 1260 DFS와 BFS NodeJs구현

목차

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

문제

 

NodeJs 구현 시 주의할 점

아래와 같이 인접리스트를 초기화해야 typeError가 나지 않는다.

let vector =  Array.from({ length: 10003 }, () => []);

 

|| 연산자를 통해 undefined가 뜨지 않도록 막아 준다.

for (let i = 0; i < nodes.length; i++) {
  vector[nodes[i][0]] = [...(vector[nodes[i][0]] || []), nodes[i][1]];
  vector[nodes[i][1]] = [...(vector[nodes[i][1]] || []), nodes[i][0]];
}

 

sort안에 정확히 명시 해주어야 오류가 안난다. 출력은 잘되더라도 백준에서는 틀리게 된다..

for(let i=1; i<=N; i++){
  if(vector[i])
    vector[i].sort((a,b)=> a-b);
}

 

코드 구현

const input = require("fs")
  .readFileSync("../test.txt", "utf-8")
  .trim()
  .split("\n");
let order = input[0].split(" ").map(Number);
input.splice(0, 1);
let nodes = [];
for (let i = 0; i < input.length; i++) {
  nodes.push(input[i].trim().split(" ").map(Number));
}
let [N, M, V] = order;

let vector =  Array.from({ length: 10003 }, () => []);
let visit = new Array(10003).fill(0);

function dfs(cur) {
  process.stdout.write(`${String(cur)} `);

  visit[cur] = 1;
  for (let i = 0; i < vector[cur].length; i++) {
    if (!visit[vector[cur][i]]) {
      dfs(vector[cur][i]);
    }
  }
}
let queue = [];

function bfs(start) {
  queue.push(start);
  visit[start] = 1;
  while (queue.length) {
    let cur = queue.shift();
    process.stdout.write(`${String(cur)} `);
    for (let i = 0; i < vector[cur].length; i++) {
      if (visit[vector[cur][i]]) continue;
      queue.push(vector[cur][i]);
      visit[vector[cur][i]] = 1;
    }
  }
}

for (let i = 0; i < nodes.length; i++) {
  vector[nodes[i][0]] = [...(vector[nodes[i][0]] || []), nodes[i][1]];
  vector[nodes[i][1]] = [...(vector[nodes[i][1]] || []), nodes[i][0]];
}

for(let i=1; i<=N; i++){
  if(vector[i])
    vector[i].sort((a,b)=> a-b);
}
dfs(V);
visit.fill(0);
console.log();
bfs(V);