[11724] 연결 요소의 개수 (JAVA)

# 문제 설명

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

---

출력

첫째 줄에 연결 요소의 개수를 출력한다.

 

# 정답 코드

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

public class Main {
    static boolean[] visited; //방문 체크 배열(1~N)
    static ArrayList<Integer>[] A; //인접 리스트(1~N)

    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()); //간선의 개수

        visited = new boolean[N+1];
        A = new ArrayList[N+1];
        for (int n = 1; n <= N; n++) {
            A[n] = new ArrayList<>();
        }

        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            A[u].add(v);
            A[v].add(u);
        }

        int cnt = 0; //연결 요소 개수
        for (int n = 1; n <= N; n++) {
            if (!visited[n]) {
                cnt++;
                dfs(n);
            }
        }

        System.out.print(cnt);
    }

    public static void dfs(int v) {
        if (visited[v]) {
            return;
        }

        visited[v] = true;
        for (int i : A[v]) {
            dfs(i);
        }
    }
}

 

dfs를 사용하여 연결 요소 개수를 구한다.

연결 요소는 에지로 연결된 노드의 집합이다.

한 번의 dfs가 끝날 때까지 탐색한 모든 노드 집합을 하나의 연결 요소로 판단하면 된다.

 

dfs를 위한 인접 리스트, 방문 체크 배열을 만든다.

양방향 그래프이므로 인접 리스트에 양쪽으로 추가한다.

연결 요소 개수를 cnt에 저장한다.

1부터 N까지 순회하며 현재 노드가 방문하지 않은 노드이면 cnt를 1 증가하고 dfs를 실행한다.

 

dfs 함수는 현재 노드 v가 방문한 노드이면 종료하고, 방문하지 않은 노드이면 방문 체크 배열을 true로 바꾼 다음 v의 인접 노드를 탐색한다.