🧑🏻‍💻 문제

코드 (BFS 와 DFS 활용)

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

public class Main {

    // 방문 여부를 저장하는 배열
    static boolean visited[];
    // 그래프의 인접 리스트
    static ArrayList<Integer>[] A;
    // BFS를 위한 큐
    static Queue<Integer> q = new LinkedList<Integer>();

    // 깊이 우선 탐색 (DFS) 메서드
    private static void DFS(int a) {
        visited[a] = true; // 현재 노드를 방문 표시

        // 현재 노드에 연결된 모든 노드를 확인
        for (int x : A[a]) {
            if (!visited[x]) { // 방문하지 않은 노드라면
                DFS(x); // 해당 노드에 대해 DFS 재귀 호출
            }
        }
    }

    // 너비 우선 탐색 (BFS) 메서드
    private static void BFS(int a) {
        visited[a] = true; // 현재 노드를 방문 표시
        q.add(a); // 큐에 현재 노드를 추가

        // 큐가 비어있지 않은 동안 반복
        while(!q.isEmpty()) {
            int b = q.poll(); // 큐에서 노드를 꺼냄

            // 현재 노드에 연결된 모든 노드를 확인
            for (int x : A[b]) {
                if (!visited[x]) { // 방문하지 않은 노드라면
                    visited[x] = true; // 방문 표시
                    q.add(x); // 큐에 추가
                }
            }
        }
    }

    public static void main (String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 노드의 수
        int M = Integer.parseInt(st.nextToken()); // 간선의 수
        A = new ArrayList[N+1]; // 인접 리스트 초기화
        visited = new boolean[N+1]; // 방문 배열 초기화

        // 인접 리스트의 각 리스트 초기화
        for (int i = 1; i < N+1; i++) {
            A[i] = new ArrayList<Integer>();
        }

        // 간선 정보를 입력받아 인접 리스트에 추가
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            A[a].add(b); // 양방향 간선
            A[b].add(a); // 양방향 간선
        }

        int count = 0; // 연결 요소의 개수를 세는 변수

        // 모든 노드에 대해 방문 여부를 확인하며 BFS 수행
        for (int i = 1; i < N+1; i++) {
            if (!visited[i]) { // 방문하지 않은 노드라면
                BFS(i); // 해당 노드에서 BFS 수행
                count++; // 연결 요소의 개수 증가
            }
        }

        System.out.println(count); // 연결 요소의 개수 출력
    }
}