[백준] 11724 연결 요소의 개수 | DFS, BFS, 그래프 | 실버 Ⅱ | JAVA

📌 문제

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

 

⭐ 해결 방법

• 그래프를 인접 리스트로 표현.
• DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)로 모든 정점을 방문.
• 방문한 정점과 방문하지 않은 정점을 기준으로 연결 요소를 구분.
• 그래프 탐색을 통해 모든 정점을 방문하고, 방문하지 않은 새로운 정점 발견 시 연결 요소 개수 증가.
• 탐색 알고리즘으로 DFS를 선택.

 

✅ 정답 코드

import java.util.*;

public class ConnectedComponents {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 입력 받기
        int n = sc.nextInt(); // 정점의 개수
        int m = sc.nextInt(); // 간선의 개수
        
        // 그래프 초기화
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 간선 입력 받기
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph.get(u).add(v);
            graph.get(v).add(u); // 무방향 그래프이므로 양쪽 추가
        }
        
        // 방문 여부 배열
        boolean[] visited = new boolean[n + 1];
        int components = 0;
        
        // DFS로 연결 요소 탐색
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                dfs(i, graph, visited);
                components++; // 새로운 연결 요소 발견
            }
        }
        
        // 결과 출력
        System.out.println(components);
    }
    
    private static void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, graph, visited);
            }
        }
    }
}

 

🗒️ 코드 설명

1. 그래프 입력 및 초기화:
   • 입력으로 주어진 정점 NNN과 간선 MMM을 사용하여 인접 리스트로 그래프를 구성합니다.
   • 무방향 그래프이므로 양쪽 정점 간 연결을 추가합니다.
2. DFS 탐색:
   • 방문 여부를 기록하는 visited 배열 사용.
   • 정점 iii에서 탐색을 시작하고 연결된 모든 정점을 재귀적으로 방문.
3. 연결 요소 개수:
   • 방문하지 않은 정점 발견 시, 새로운 연결 요소를 찾았으므로 components 값을 증가.
4. 출력:
   • 최종적으로 연결 요소 개수를 출력.