[백준/C++] 11724번: 연결 요소의 개수 - DFS와 인접 리스트의 정석

1. 문제 정보

• 문제 번호: 11724번
• 문제 이름: 연결 요소의 개수
• 문제 요약: 방향 없는 그래프가 주어졌을 때, 연결 요소(덩어리)의 개수를 구하라.

---

2. 결정적 문법: [] vs () 의 차이

① vector<int> graph[1001]; (배열의 각 칸이 벡터)

• 정체: vector<int> 타입의 객체 1001개를 담는 "배열"입니다.
• 용도: 그래프의 인접 리스트(Adjacency List)를 구현할 때 표준적으로 사용됩니다.
• graph[1]은 1번 정점과 연결된 정점들을 담는 벡터, graph[2]는 2번 정점과 연결된 정점들을 담는 벡터가 되는 식.

② vector<int> graph(1001); (크기가 1001인 하나의 벡터)

• 정체: 정수(int) 1001개를 담을 수 있는 "하나의 벡터"이다.
• 용도: 1차원 배열처럼 사용하고 싶을 때 쓴다. 만약 이걸로 인접 리스트를 만들고 싶다면 vector<vector<int>> graph(1001);처럼 선언해야 한다.

---

3. 알고리즘: 연결 요소 찾기 (DFS)

연결 요소는 쉽게 말해 "섬(Island)"과 같다.

1. 전체 탐색: 1번 정점부터 N번 정점까지 차례대로 확인합니다.
2. 새로운 섬 발견: 아직 방문하지 않은(!visited) 정점을 발견했다면, 새로운 연결 요소가 시작된 것이다. connected++를 해준다.
3. 섬 전체 마킹: DFS(깊이 우선 탐색)를 시작하여 해당 정점과 연결된 모든 정점을 방문 처리(visited = true)합니다.
4. 반복: 모든 정점을 확인할 때까지 반복합니다.

---

4. 코드 구현

#include <iostream>
#include <vector>

using namespace std;

// 1. 인접 리스트 선언 (배열의 각 칸이 벡터)
vector<int> graph[1001]; 
bool visited[1001] = {false};

void dfs(int start) {
    visited[start] = true;
    
    // 범위 기반 for문으로 연결된 정점 확인
    for(int v : graph[start]) {
        if(!visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    // 2. 간선 정보 입력 (무방향 그래프이므로 양방향 추가)
    for(int i = 0; i < M; i++) {
        int v, p;
        cin >> v >> p;
        graph[v].push_back(p);
        graph[p].push_back(v);
    }

    int connected = 0;

    // 3. 모든 정점을 순회하며 DFS 실행
    for(int i = 1; i <= N; i++) {
        if(!visited[i]) {
            dfs(i);        // DFS가 한 번 끝날 때마다 섬 하나를 다 찾은 것
            connected++;   // 연결 요소 개수 증가
        }
    }

    cout << connected << "\n";
    
    return 0;
}

---

5. 배운 점 & 회고 (TIL) ✍️

1. C++ 문법의 재발견: [] vs ()

그래프를 구현할 때 사용하는 vector 선언 방식에 따라 메모리 구조가 완전히 달라짐을 이해해야 한다.

• vector<int> graph[1001]: 이는 vector<int> 타입의 객체 1001개를 담는 배열이다. 각 인덱스가 하나의 정점을 의미하며, 해당 정점에 연결된 이웃 노드들을 벡터 안에 저장하는 인접 리스트 구현에 최적화된 방식이다.
• vector<int> graph(1001): 이는 정수(int) 1001개를 저장할 수 있는 단 하나의 벡터를 생성하는 방식이다. 주로 1차원 배열이 필요할 때 사용한다.
• 정점의 개수가 고정적인 문제에서는 []를 이용한 배열 선언이 직관적이며 성능 면에서도 유리하다.

---

2. 그래프를 저장하는 두 가지 방법

그래프 자료구조를 메모리에 올리는 방법은 크게 두 가지로 나뉜다.

구분	인접 리스트 (Adjacency List)	인접 행렬 (Adjacency Matrix)
선언 방식	vector<int> graph[N]	int graph[N][N]
메모리 복잡도	O(V+E) (실제 간선만큼 사용)	O(V^2) (무조건 정점의 제곱)
탐색 시간	O(degree(v)) (이웃만 확인)	O(V) (모든 칸 확인)
주요 장점	메모리 효율적, 희소 그래프에 유리	두 노드의 연결 여부를 O(1)에 확인

왜 인접 리스트가 '국룰'인가?

본 문제에서 정점(N)이 1,000개일 때, 인접 행렬은 연결 여부와 상관없이 1,000,000개의 칸을 확인해야 한다. 반면 인접 리스트는 실제로 연결된 간선(M) 정보만 저장하고, DFS 탐색 시 실제로 존재하는 이웃만 쏙쏙 골라 방문한다. 따라서 데이터가 커질수록 시간과 공간 복잡도 면에서 압도적인 효율을 보여준다.

---

3. 핵심 로직: "방문 처리"와 "덩어리 찾기"

① 방문 처리(Visited)의 중요성

이미 방문한 정점을 다시 방문하지 않도록 막는 visited 배열은 DFS/BFS의 핵심이다. 이는 무한 루프를 방지할 뿐만 아니라, 하나의 시작점으로부터 갈 수 있는 모든 정점을 탐색하여 독립된 덩어리(연결 요소)를 정확히 구분해내는 역할을 한다.

② '유기농 배추' 문제와의 본질적 공통점

이전에 풀었던 1012번(유기농 배추) 문제와 본 문제의 논리는 동일하다.

• 유기농 배추: 2차원 격자(Grid) 내에서 상하좌우로 연결된 덩어리를 찾음이다.
• 연결 요소의 개수: 인접 리스트(Graph) 상에서 간선으로 연결된 덩어리를 찾음이다.
• 데이터의 표현 방식만 다를 뿐, "연결된 그룹의 개수를 세는 것"이 문제의 본질임을 이해하는 것이 중요하다.

---

4. 결론 및 회고

그래프 문제에서 자료구조의 선택이 알고리즘의 효율성을 결정짓는다는 것을 체감하였다. 특히 인접 리스트의 경제적인 메모리 사용과 빠른 탐색 속도는 대규모 그래프 문제를 해결하는 데 필수적인 요소이다. 또한, 격자형 탐색과 그래프 탐색이 결국 '연결 요소 찾기'라는 하나의 원리로 관통한다는 점을 배웠다.