[백준 | 실버 3 | JavaScript] 2606번, 바이러스

 

Link

2606번 - 바이러스

 

---

문제

풀이

(1) 재귀 DFS

var input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const N = Number(input[0]);
const graph = Array.from({ length: N + 1 }, () => []);

for (let i = 2; i < input.length; i++) {
  let [node1, node2] = input[i].split(" ").map(Number);
  graph[node1].push(node2);
  graph[node2].push(node1);
}

let answer = 0;
function dfsRecursive(graph, node, visited = {}) {
  visited[node] = true;
  answer += 1;

  for (let g of graph[node]) {
    if (visited[g]) continue;

    dfsRecursive(graph, g, visited);
  }
}

dfsRecursive(graph, 1);

console.log(answer - 1);

(2) 스택 DFS

var input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const N = Number(input[0]);
const graph = Array.from({ length: N + 1 }, () => []);

for (let i = 2; i < input.length; i++) {
  let [node1, node2] = input[i].split(" ").map(Number);
  graph[node1].push(node2);
  graph[node2].push(node1);
}

let answer = 0;

function dfsStack(graph, node) {
  let visited = {};
  let stack = [];

  stack.push(node);

  while (stack.length > 0) {
    let g = stack.pop();

    if (visited[g]) continue;
    visited[g] = true;
    answer += 1;

    for (let n of graph[g]) {
      if (visited[n]) continue;
      stack.push(n);
    }
  }
}

dfsStack(graph, 1);

console.log(answer - 1);

(3) BFS

let input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

let idx = 0;
const COMPUTERS = Number(input[idx++]);
const CONNECTIONS = Number(input[idx++]);
const graph = Array.from({ length: COMPUTERS + 1 }, () => []);

let answer = 0;

for (let c = 0; c < CONNECTIONS; c++) {
  const [c1, c2] = input[idx++].split(" ").map(Number);

  graph[c1].push(c2);
  graph[c2].push(c1);
}

const bfs = (start) => {
  const visited = {};
  const queue = [];

  queue.push(start);
  visited[start] = true;

  while (queue.length > 0) {
    const node = queue.shift();

    for (let g of graph[node]) {
      if (visited[g]) continue;

      visited[g] = true;
      queue.push(g);
      answer += 1;
    }
  }
};

bfs(1);

console.log(answer);