연결 요소의 개수 문제 풀이 - DFS로 그래프 탐색하기

문제 소개

백준 11724번 "연결 요소의 개수" 문제를 풀어보겠습니다. 방향 없는 그래프에서 연결 요소(Connected Component)의 개수를 구하는 기본적인 그래프 탐색 문제입니다.

문제 요약:

• 정점의 개수 N (1 ≤ N ≤ 1,000)
• 간선의 개수 M (0 ≤ M ≤ N×(N-1)/2)
• 각 간선은 정점 u와 v를 연결 (1 ≤ u, v ≤ N)

접근 방법

연결 요소란 서로 연결된 정점들의 집합을 의미합니다. 모든 정점을 순회하면서 아직 방문하지 않은 정점에서 DFS를 시작할 때마다 새로운 연결 요소를 발견한 것입니다.

알고리즘 과정

1. 모든 정점에 대해 방문 여부를 확인
2. 방문하지 않은 정점이 있으면 해당 정점에서 DFS 시작
3. DFS로 연결된 모든 정점을 방문 처리
4. 연결 요소 개수 +1
5. 모든 정점을 확인할 때까지 반복

코드 구현

#include <bits/stdc++.h>
using namespace std;

bool vis[100001];
vector<vector<int>> g(100001);
int cnt = 0;

void dfs(int cur){
    vis[cur] = true;
    
    for(auto nxt : g[cur]){
        if(vis[nxt]) continue;
        dfs(nxt);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int v, e;
    cin >> v >> e;
    
    for(int i = 0; i < e; i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);  // 무방향 그래프이므로 양방향 추가
    }
    
    for(int i = 1; i <= v; i++){
        if(!vis[i]){
            cnt++;
            dfs(i);
        }
    }
    
    cout << cnt;
    
    return 0;
}

실수했던 부분들

1. 반복문 범위 실수

처음에는 이렇게 작성했었습니다:

// 잘못된 코드
for(int i = 1; i < e; i++){  // 첫 번째 간선 건너뛰고, 마지막 간선 누락
    // ...
}

for(int i = 1; i < v; i++){  // 마지막 정점 v 누락
    // ...
}

문제점:

• 간선 입력에서 첫 번째 간선을 건너뛰고 마지막 간선을 읽지 못함
• 정점 탐색에서 마지막 정점을 확인하지 않음

해결책:

for(int i = 0; i < e; i++){    // 0부터 e-1까지 (총 e개)
for(int i = 1; i <= v; i++){   // 1부터 v까지 (모든 정점)

2. 0-based vs 1-based 인덱싱

문제에서 정점 번호가 1부터 시작하는데, 처음에는 0부터 확인해서 틀렸습니다.

// 잘못된 코드
for(int i = 0; i < v; i++){  // 정점 0 확인 (존재하지 않음)

정점 0은 실제로 존재하지 않지만 방문하지 않은 상태로 카운트되어 연결 요소 개수가 +1 되는 문제가 발생했습니다.

시간 복잡도

• 시간 복잡도: O(V + E)
  • 모든 정점을 한 번씩 방문: O(V)
  • 모든 간선을 한 번씩 탐색: O(E)
• 공간 복잡도: O(V + E)
  • 인접 리스트: O(E)
  • 방문 배열: O(V)

마무리

그래프 탐색 문제에서는 인덱스 범위를 정확히 파악하는 것이 중요합니다. 특히 문제에서 정점 번호가 몇 번부터 시작하는지, 몇 개의 데이터를 입력받아야 하는지 꼼꼼히 확인해야 합니다.

DFS를 이용한 연결 요소 찾기는 그래프 이론의 기본이 되는 중요한 개념이므로, 이 패턴을 잘 익혀두면 다른 그래프 문제에도 응용할 수 있을 것입니다.