[백준저지] 11724번 : 연결 요소의 개수

www.acmicpc.net/problem/11724

1. 문제

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

입)

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

출)

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

2. 풀이

import java.util.*;

public class Main {
	// DFS를 이용해서 처리한다.
    public static void dfs(ArrayList<Integer>[] a, boolean[] c, int x) {
        // 방문했으면 return
        if (c[x]) {
            return;
        }
        // 방문했다고 표시
        c[x] = true;
        // 인접리스트를 loop하면서
        for (int y : a[x]) {
        	// 방문 안한 노드 계속 dfs한다
            if (c[y] == false) {
                dfs(a, c, y);
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        // 정점의 개수
        int n = sc.nextInt();
        // 간선의 개수
        int m = sc.nextInt();
        ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n+1];
        // 인접리스트
        for (int i=1; i<=n; i++) {
            a[i] = new ArrayList<Integer>();
        }
        // 간선 세팅
        for (int i=0; i<m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            a[u].add(v);
            a[v].add(u);
        }
        // 방문 여부 배열
        boolean[] check = new boolean[n+1];
        int ans = 0;
        for (int i=1; i<=n; i++) {
            if (check[i] == false) {
                dfs(a, check, i);
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}

DFS를 이용해서 DFS를 반복해서 처리하여, 방문 배열에 방문 안 한 노드를 시작으로 DFS 완료할 때마다 ans += 1 해줌으로써 연결 요소의 개수를 카운트한다.