[백준 11724] 연결 요소의 개수 (Java)

🚀 문제 분석

• 핵심 과제: 방향 없는 그래프가 주어졌을 때, 서로 연결된 정점들의 집합(연결 요소, Connected Component)이 몇 개인지 구하는 문제입니다.
• 데이터 규모: 정점 $N \le 1,000$, 간선 $M \le 500,000$.
• 알고리즘 선택: 모든 노드를 확인해야 하므로 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 사용하여 방문하지 않은 노드부터 탐색을 시작할 때마다 카운트를 올리면 됩니다.

💡 해결 전략: DFS와 방문 배열

그래프가 하나로 꽉 연결되어 있지 않고 여러 뭉텅이로 나뉘어 있을 수 있습니다.

1. 인접 리스트 구축: 메모리 효율과 탐색 속도를 위해 ArrayList 배열로 그래프를 표현합니다.
2. 순회하며 탐색 시작: 1번 노드부터 $N$번 노드까지 루프를 돕니다.
3. 새로운 덩어리 발견: 현재 노드를 아직 방문하지 않았다면(!visited[i]), 새로운 연결 요소를 찾은 것이므로 count를 증가시키고 DFS를 시작합니다.
4. 연결된 모든 노드 마킹: DFS 내부에서는 연결된 모든 노드를 방문 처리하여, 메인 루프에서 같은 덩어리를 중복 카운트하지 않게 합니다.

💻 구현 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static boolean[] visited;
    static int count = 0;

    public static void main(String[] args) throws Exception {
	    int N = nextInt(), M = nextInt();

        // 1. 인접 리스트 초기화
        List<Integer>[] graph = new List[N + 1];
        for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();

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

        visited = new boolean[N + 1];

        // 3. 모든 노드를 순회하며 탐색되지 않은 '덩어리' 찾기
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                dfs(graph, i);
                count++; // DFS가 한 번 끝날 때마다 연결 요소 +1
            }
        }
        System.out.println(count);
    }

    static void dfs(List<Integer>[] graph, int node) {
        visited[node] = true;

        for (int next : graph[node]) {
            if (!visited[next]) {
                dfs(graph, next);
            }
        }
    }

    static int nextInt() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return Integer.parseInt(st.nextToken());
    }
}

🧐 기술적 고찰

• 인접 행렬 vs 인접 리스트: 정점은 1,000개인데 간선은 최대 50만 개입니다. 인접 행렬($N^2$)도 가능은 하지만, 간선이 많은 경우 인접 리스트를 사용하는 것이 탐색 시 불필요한 루프를 줄이는 데 유리합니다.
• 재귀 깊이(Recursion Depth): $N=1,000$ 정도면 Java의 기본 스택 사이즈로 충분히 DFS 처리가 가능합니다. 만약 $N$이 훨씬 크다면 Stack 자료구조를 이용한 반복문 DFS나 BFS를 고려해야 합니다.
• 연결 요소의 의미: 이 로직은 나중에 '섬 개수 구하기'나 '영역 넓이 구하기' 같은 문제의 가장 기본 베이스가 됩니다.