[백준] 1062번: 연결 요수의 개수 (JavaScript)

---

문제

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

개념

그래프 탐색

DFS, BFS

구현 코드(JavaScript)

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

const [n, m] = input[0].split(' ').map(Number);
const graph = Array(n + 1)
  .fill(0)
  .map(() => Array(n + 1).fill(0));

for (let i = 1; i <= m; i++) {
  const [u, v] = input[i].split(' ').map(Number);
  graph[u].push(v);
  graph[v].push(u);
}

let count = 0;
const visited = Array(n + 1).fill(false);

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

  while (queue.length) {
    const node = queue.shift();
    for (let i = 0; i < graph[node].length; i++) {
      const nextNode = graph[node][i];
      if (!visited[nextNode]) {
        visited[nextNode] = true;
        queue.push(nextNode);
      }
    }
  }
};

for (let i = 1; i <= n; i++) {
  if (!visited[i]) {
    bfs(i);
    count++;
  }
}

console.log(count);

코드 설명

주어진 무방향 그래프에서 연결 요소의 개수를 구하는 문제입니다.

그래프는 가중치가 없는 형태이며, 이는 BFS를 사용하기에 적절한 구조입니다.

BFS를 선택한 이유?

• 무방향 그래프에서 연결 요소의 개수를 찾는 문제는 DFS와 BFS를 사용하여 해결할 수 있습니다.
• BFS는 큐(Queue) 를 사용하여 탐색하기 때문에, DFS에 비해 재귀 호출의 깊이가 깊어지는 문제를 방지할 수 있습니다.
• 일반적으로 인접 행렬을 사용하면 BFS의 시간 복잡도는 O(N^2) 입니다.

입력 및 그래프 표현

입력값을 받아 2차원 인접 행렬을 생성합니다. 이를 통해 연결된 노드를 쉽게 탐색할 수 있도록 합니다.

일반적으로 탐색해야 하는 그래프의 노드가 n개라면, 인접 행렬은 n * n 의 크기로 만듭니다.

 

입력 예시

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

인접 행렬 표현

위 입력 예제를 기준으로 만든 인접 행렬은 다음과 같습니다.

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

 

위 행렬 정보에 따르면 다음과 같이 연결되었다고 할 수 있습니다!

1 - 2 - 5    (첫 번째 연결 요소)
3 - 4 - 6    (두 번째 연결 요소)

 

 

 

1. i = 1일 때, visited[1]이 false이므로 bfs(1) 실행 → 1, 2, 5 방문 -> count++ ( i = 2, 5는 이미 방문했으므로 건너뜀 )
2. i = 3일 때, visited[3]이 false이므로 bfs(3) 실행 → 3, 4, 6 방문 → count++

=> 따라서, 최종적으로 카운팅하여 출력되는 값은 2입니다 😄

 

 

너비 우선 탐색(BFS) 과정 

1. 그래프 초기화
   • graph 배열을 생성하여 인접 행렬을 만듭니다.
   • graph[u].push(v)와 graph[v].push(u)를 통해 무방향 간선을 저장합니다.
2. 방문 여부를 체크할 배열 생성
   • visited 배열을 false로 초기화하여 방문 여부를 추적합니다.
3. BFS 탐색 함수 구현
   • queue를 이용하여 BFS를 수행합니다.
   • 현재 노드를 queue에서 꺼내고 방문 처리한 후, 연결된 노드들을 큐에 추가합니다.
   • 위 과정을 큐에 남은 노드가 없을 때까지 반복합니다.
4. 모든 노드를 순회하며 연결 요소 개수 계산
   • 방문하지 않은 노드를 발견하면 BFS를 실행하고 count를 증가시킵니다.
   • 방문하지 않은 노드를 발견했다는 건 이 노드가 아직 탐색되지 않은 새로운 연결 요소에 속해 있다는 뜻입니다.
   • 따라서 bfs(i)를 실행하여 해당 노드와 연결된 모든 노드를 방문 처리합니다.
     • count++를 실행하여 새로운 연결 요소를 발견했다는 사실을 기록합니다.

---