[백준 11724] 연결 요소의 개수 with Node.js

문제 링크

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

11724번: 연결 요소의 개수

풀이

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

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
  }
}

class Stack {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  push(...values) {
    values.forEach(value => {
      const node = new Node(value)
      if (!this.head) this.head = node;
      node.prev = this.tail;
      this.tail = node;
      this.size++;
    });
  }
  pop() {
    if (this.size) {
      const node = this.tail;
      this.tail = node.prev;
      this.size--;
      return node.value;
    }
    return -1;
  }
  clear() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
}

const dfs = function (graph, start, visited, stack) {
  if (graph[start].length === 0) {
    visited[start] = true;
    return;
  }
  stack.clear();
  stack.push(start);
  while (stack.size) {
    const node = stack.pop();
    if (!visited[node]) {
      visited[node] = true;
      stack.push(...graph[node]);
    }
  }
}

const solve = function () {
  const [N, M] = input.shift().split(' ').map(v => +v);
  const graph = Array.from({length: N+1}, v => []);
  const visited = Array(N+1).fill(false);
  const stack = new Stack();
  input.forEach(uv => {
    const [u, v] = uv.split(' ');
      graph[+u].push(+v);
      graph[+v].push(+u);
  });
  let count = 0;
  for (i=1; i<=N; ++i) {
    if (!visited[i]) {
      dfs(graph, i, visited, stack);
      ++count;
    }
  }
  console.log(count);
}
solve();

N개의 노드를 1부터 N까지의 값을 가지는 노드로 간주하고

graph의 1~N번째 인덱스에 각각 해당 노드에 연결된 다른 노드들을 저장한다.

visited에는 1~N번째 인덱스에 각각 해당 노드의 방문 여부를 저장한다. 초기값은 false이다.

 

1부터 N까지 반복문을 돌리면서 아직 방문하지 않은 노드에 대해서만 dfs를 실행한다.

bfs에서는 현재 노드를 stack에 추가한 다음, stack이 완전히 빌 때 까지 아래의 작업을 반복 실행한다.

 

1. stack을 pop한다. 이 때, pop된 노드를 node라고 하겠다.

2. node를 아직 방문하지 않았다면, node의 방문 여부를 갱신하고

     node에 연결된 모든 다른 노드들을 stack에 push한다.

 

위 과정을 거치면 start 노드에 연결된 모든 노드들을 방문하게 된다.

dfs의 실행횟수는 곧 전체 그래프의 연결 요소의 개수와 같다.