백준) 11724 - 연결 요소의 개수 JS

📌 문제 링크

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

---

📌 문제 탐색하기

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

시간복잡도

• 노드 수와 간선 수에 따라 선형적으로 증가하므로 O(n+m)

알고리즘 선택

• DFS

---

📌 코드 설계하기

1. 문제의 `input`을 개행으로 분리합니다.
2. `input` 값을 공백으로 분리하여 숫자로 변환합니다.
3. `inputs` 배열에서 노드 수 `n`과 간선 수 `m`으로 분리하고 배열의 첫번째 요소를 제거하고 반환합니다.
4. 연결된 컴포넌트의 개수를 세기 위해 `answer` 변수를 `0`으로 초기화 합니다.
5. 각 노드의 방문 여부를 기록하기 위해 `visited`배열을 생성하여 `false`로 초기화합니다.
6. 무방향 그래프를 표현하기 위해 `graph`배열을 생성합니다.
7. `inputs` 배열을 순회하면서 각 간선`from, to`을 그래프에 추가합니다. 이때, 무방향 그래프이므로 `from`의 배열에 `to`를 추가하고, `to`의 배열에도 `from`을 추가합니다.
8. `dfs`함수를 정의 합니다.
9. 주어진 `start` 노드를 방문했다고 표시하고, 해당 노드와 연결된 모든 노드 `next`를 순회합니다.
10. 연결된 노드가 방문되지 않았다면, 재귀적으로 `dfs`를 호출합니다.
11. 모든 노드를 순회하면서, 방문하지 않은 노드가 있을 경우 `dfs`를 호출합니다.
12. `dfs` 호출이 끝난 후에는 연결된 컴포넌트를 하나 발견했으므로 `answer`를 증가시킵니다.
13. 최종적으로 발견한 연결된 컴포넌트의 개수를 출력합니다.

---

📌 정답 코드

//https://www.acmicpc.net/problem/11724
export {};

const fs = require('fs');
const filePath =
  process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input2.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');
const inputs = input
  .slice()
  .map((x: string) => x.split(' ').map(Number));
const [n, m] = inputs.shift()!;

let answer = 0;
const visited = Array(n + 1).fill(false);
const graph = Array.from({ length: n + 1 }, () => []);

// 양방향(무방향) 그래프 만들기
for (const [from, to] of inputs) {
  graph[from].push(to);
  graph[to].push(from);
}

const dfs = (start: number) => {
  visited[start] = true;
  for (const next of graph[start]) {
    if (!visited[next]) {
      dfs(next);
    }
  }
};

// 연결된 컴포넌트 수 세기
for (let i = 1; i <= n; i++) {
  if (!visited[i]) {
    dfs(i);
    // 새로운 연결된 컴포넌트를 발견할 때마다 카운트 증가
    answer++;
  }
}

console.log(answer);