[백준 | 실버 2 | JavaScript] 11724번, 연결 요소의 개수

 

Link

11724번 - 연결 요소의 개수

 

---

문제

풀이

(1) 재귀 구현

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

let idx = 0;

const [N, M] = input[idx++].split(" ").map(Number);
const graph = Array.from({ length: N + 1 }, () => []);
const visited = Array.from({ length: N + 1 }, () => false);
let answer = 0;

for (let m = 0; m < M; m++) {
  const [node1, node2] = input[idx++].split(" ").map(Number);

  graph[node1].push(node2);
  graph[node2].push(node1);
}

const dfsRecursive = (node) => {
  visited[node] = true;

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

    dfs(g);
  }
};

for (let n in graph) {
  if (visited[n]) continue;

  dfsRecursive(n);
  answer += 1;
}

console.log(answer - 1);

(2) 스택 구현

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

let idx = 0;

const [N, M] = input[idx++].split(" ").map(Number);
const graph = Array.from({ length: N + 1 }, () => []);
const visited = Array.from({ length: N + 1 }, () => false);
let answer = 0;

for (let m = 0; m < M; m++) {
  const [node1, node2] = input[idx++].split(" ").map(Number);

  graph[node1].push(node2);
  graph[node2].push(node1);
}

const dfsStack = (node) => {
  const stack = [node];

  while (stack.length > 0) {
    const n = stack.pop();
    if (visited[n]) continue;

    visited[n] = true;
    for (let g of graph[n]) {
      if (visited[g]) continue;

      stack.push(g);
    }
  }
};

for (let n in graph) {
  if (visited[n]) continue;

  dfsStack(n);
  answer += 1;
}

console.log(answer - 1);

(3) BFS 구현

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

let idx = 0;

const [N, M] = input[idx++].split(" ").map(Number);
const graph = Array.from({ length: N + 1 }, () => []);
let answer = 0;

for (let m = 0; m < M; m++) {
  const [u, v] = input[idx++].split(" ").map(Number);

  graph[u].push(v);
  graph[v].push(u);
}

const visited = {};

const bfs = (start) => {
  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;

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

for (let k = 1; k <= N; k++) {
  if (visited[k]) continue;

  bfs(k);
  answer += 1;
}

console.log(answer);