💡문제 분석 요약

• 무방향 그래프에서 연결 요소의 개수를 구하는 문제
• 입력으로 주어진 그래프의 노드와 간선 정보를 통해, 연결된 부분 그래프가 몇 개 있는지 계산하는 것이 목표이다.
• 연결 요소는 그래프에서 서로 연결된 노드들의 집합을 말한다.
• 노드가 1부터 n까지 있으며, 두 노드가 간선으로 연결되어 있으면 같은 연결 요소에 속하게 된다.

💡알고리즘 설계

• 그래프 표현
  • 주어진 그래프는 인접 리스트를 사용하여 표현한다.
  • 각 노드에 대해 연결된 노드들의 리스트를 만들어 간선 정보를 저장한다.
• DFS(깊이 우선 탐색)
  • 그래프 탐색에는 DFS를 사용한다.
  • DFS는 한 노드에서 시작해 해당 노드와 연결된 모든 노드를 탐색하며, 같은 연결 요소에 속한 노드들을 방문하게 된다.
• 방문 여부 체크
  • 각 노드가 이미 방문되었는지 확인하기 위해 visited 배열을 사용한다.
  • 방문하지 않은 노드를 발견하면, 새로운 연결 요소로 간주하고 DFS를 통해 해당 연결 요소의 모든 노드를 탐색한다.
• 연결 요소 개수 계산
  • 각 노드에 대해 DFS를 수행하며, 방문하지 않은 노드가 있을 때마다 연결 요소의 개수를 1씩 증가시킨다.

💡코드

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim().split('\\n')

const [n, m] = input[0].split(' ').map(Number); 
// n: 노드 수, m: 간선 수

const graph = Array.from({ length: n + 1 }, () => []); 
// 노드끼리 연결된 정보를 저장할 인접 리스트
// - 노드 번호가 1부터 시작하기 때문에 length: n + 1

// 그래프 구축
for (let i = 1; i <= m; i++) {
  const [u, v] = input[i].split(' ').map(Number); 
  // 두 번째 줄부터 간선 정보 가져오기

  graph[u].push(v); 
  // u의 배열에 v를 추가(= 노드 u와 노드 v가 연결됨)

  graph[v].push(u); 
  // 반대로 v의 배열에 u를 추가
}

// 노드가 방문했는지 여부를 기록
const visited = Array(n + 1).fill(false); 

// DFS 함수
const dfs = (node) => {
  // 현재 노드를 방문했는지 기록
  visited[node] = true;

  // 현재 노드와 연결된 노드들(neighbor)을 차례대로 탐색
  for (let neighbor of graph[node]) {

    // 방문하지 않은 neighbor가 있다면
    if (!visited[neighbor]) {
      // 그 노드에 대해 다시 dfs(neighbor)를 호출하여 계속해서 연결된 노드들을 탐색
      dfs(neighbor);
    }
  }
};

// 연결 요소의 개수를 저장하는 변수
let connectedComponents = 0;

// 모든 노드에 대해 DFS 수행
for (let i = 1; i <= n; i++) {

  // 아직 방문하지 않은 노드라면
  if (!visited[i]) { 
    connectedComponents++; 
    // 연결 요소 1 증가
    
    dfs(i); 
    //  그 노드를 시작점으로 DFS 수행
  }
}

// 연결 요소의 개수 출력
console.log(connectedComponents);

💡시간복잡도

• 시간 복잡도는 O(n + m)이다.
  • n은 노드의 수, m은 간선의 수