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

DFS / BFS 모두 사용 가능한 문제다.

시간이 넉넉한 문제라면 DFS로 푸는 게 코드가 짧아져서 DFS로 풀었다.

다른 DFS 문제와는 다르게 노드들이 이어져 있지 않을 수 있어서

조금 시간이 걸렸다.

---

최종 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static int arr[][];
    static boolean visit[];
    static int answer;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n + 1][n + 1];
        visit = new boolean[n + 1];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a][b] = arr[b][a] = 1;
        }
        // 방문한적이 없다면 dfs 실행
        for (int i = 1; i < n + 1; i++) {
            if(!visit[i]) {
                dfs(i);
                answer++;
            }
        }
        System.out.println(answer);
    }
    public static void dfs(int num) {
        visit[num] = true;
        for (int i = 1; i < n + 1; i++) {
            if(!visit[i] && arr[num][i] == 1) {
                dfs(i);
            }
        }
    }
}