백준 11724 연결 요소의 개수 (node.js)

문제

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

 

문제 해석

이 문제 또한 그래프 이론 중 BFS로 쉽게 풀 수 있다.

그래프의 앞 뒤가 구분되지 않기 때문에, 앞과 뒤 모두 각 배열에 추가해주고 한번 지나간 곳을 체크해 주는 방식으로 풀면 된다.

풀이

const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

function solution(input) {
  const [N, M] = input.shift().split(" ").map(Number);
  const lines = input.map((v) => v.split(" ").map(Number));
  const visited = Array(N + 1).fill(false);
  const graph = Array.from(Array(N + 1)).map(() => []);
  let answer = 0;
  const checkArr = [];

  lines.map(([from, to]) => {
    graph[from].push(to);
    graph[to].push(from);
  });

  const bfs = (start) => {
    let queue = [start];
    while (queue.length) {
      const node = queue.shift();
      for (const vertax of graph[node]) {
        if (!visited[vertax]) {
          visited[vertax] = true;
          queue.push(vertax);
        }
      }
    }
  };

  for (let i = 1; i <= N; i++) {
    if (visited[i]) continue;
    bfs(i);
    answer++;
  }

  return answer;
}

console.log(solution(input));

 

 

끝