[알고리즘/백준] 11724번 :연결 요소의 개수(Java)

문제	11724번 :연결 요소의 개수
문제링크	https://www.acmicpc.net/problem/11724
난이도	S2
언어	Java
분류	그래프이론 | 그래프이론, 그래프탐색, 너비우선탐색, 깊이우선탐색

 

 

📌 최종 정답 코드

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

public class Main {
    // 정점의 개수와 간선의 개수를 저장할 변수
    static int n, m;
    // 그래프 인접 리스트
    static List<Integer>[] graph;
    // 방문 여부를 저장할 배열
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 첫 번째 줄: 정점의 개수 n과 간선의 개수 m을 입력받음
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 정점의 수
        m = Integer.parseInt(st.nextToken()); // 간선의 수

        // 그래프 초기화 (정점 번호는 1부터 시작하므로 n+1 크기로 생성)
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 간선 정보 입력받아서 양방향 그래프 구성
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()); // 정점 u
            int v = Integer.parseInt(st.nextToken()); // 정점 v

            // 무방향 그래프이므로 양쪽에 추가
            graph[u].add(v);
            graph[v].add(u);
        }

        // 방문 배열 초기화
        visited = new boolean[n + 1];

        int count = 0; // 연결 요소 개수 카운트 변수

        // 모든 정점에 대해 순회하며 DFS 수행
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                dfs(i);  // 방문하지 않은 정점에서 DFS 시작
                count++; // 하나의 연결 요소를 탐색 완료했으므로 개수 증가
            }
        }

        // 결과 출력
        bw.write(String.valueOf(count));
        bw.newLine();

        // 자원 정리
        bw.flush();
        bw.close();
        br.close();
    }

    // 깊이 우선 탐색 (DFS) 함수
    static void dfs(int node) {
        visited[node] = true; // 현재 노드 방문 처리

        // 현재 노드와 연결된 모든 노드를 탐색
        for (int next : graph[node]) {
            if (!visited[next]) {
                dfs(next); // 방문하지 않은 인접 노드에 대해 DFS 재귀 호출
            }
        }
    }
}

📌 구해야 하는 정답

- 첫째 줄에 연결 요소의 개수를 출력

📌 코드 설계하기

1. n, m 입력 받기
2. 인접 리스트 생성
3. 간선 정보를 바탕으로 그래프 구성
4. 방문 여부 배열 초기화
5. 모든 정점 순회:
    - 방문하지 않았으면 DFS 수행 후 count++
6. count 출력