[Javascript] 백준 11724: 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1 

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1 

2

예제 입력 2 

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2 

1

 

---

문제 풀이

백준 2606 바이러스 문제의 아주 조금 응용된 버전이다.

 

1번 예제의 연결 관계를 다음의 그래프처럼 나타낸다. 편의상 N+1개 의 배열을 만들었다.

1번인덱스는 1번 노드와 연결된 노드들의 번호이다. 나머지도 마찬가지로 n번째 인덱스는 n번 노드이고, n번노드와 연결된 노드번호를 요소로 갖고 있다. 

 

그림으로 직접 나타내보면 다음처럼 생긴 그래프이다. 연결된 요소의 갯수는 2개임을 확인할 수 있다.

 

dfs함수는 시작 노드를 설정하면 연결된 노드를 모두 순회하는 함수이다. 따라서 dfs함수가 호출될 때 마다 count를 +1을 하면 연결된 요소의 갯수를 알 수 있다.

 

 

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

const [N, M] = input.shift().split(" ").map(Number);

const graph = Array.from(Array(N + 1), () => []);
const visited = Array.from(Array(N + 1), () => false);
let count = 0;

for (let i = 0; i < M; i++) {
  const [start, end] = input[i].split(" ").map(Number);

  graph[start].push(end);
  graph[end].push(start);
}

const dfs = (start) => {
  if (!visited.includes(false)) {
    return;
  }

  for (let i of graph[start]) {
    if (visited[i] === false) {
      visited[i] = true;
      dfs(i);
    }
  }
};

for (let i = 1; i < N + 1; i++) {
  if (visited[i] === false) {
    count++;
    dfs(i);
  }
}

console.log(count);