[JAVA/백준] 11724번 : 연결 요소의 개수

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

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

<Output>

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

<examples>
-입력

6 5
1 2
2 5
5 1
3 4
4 6

-출력

2

[풀이]

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

public class Main {
    static ArrayList<Integer>[] A;
    static boolean visited[];

    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 s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            A[s].add(e);
            A[e].add(s); //양방향이므로 양쪽에 더하기
        }
        int count = 0;
        for (int i=1;i<n+1;i++){
            if (!visited[i]){
                count++;
                DFS(i);
            }
        }
        System.out.println(count);
    }

    static void DFS(int v) {
        if (visited[v]){
            return;
        }
        visited[v] = true;
        for (int i : A[v]){ //현재 노드에서 연결된 노드들 중에
            if (visited[i] == false){ //방문 안한 노드가 있다면 
                DFS(i); //다시 탐색해주세요. (깊이우선탐색, 부분이진트리 성립)
            }
        }
    }
}

 

 

---

 

방향 없는 그래프는 다르게 말해 양방향 그래프를 뜻한다.

연결 요소란, 에지로 연결된 노드의 집합을 말하며,

한번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 <연결 요소>로 판단할 수 있다.

우선 그래프를 입력받아 인접리스트로 저장하고 방문 배열을 최초로 초기화한다.

방향이 없으므로 양쪽 방향으로 모두 에지를 저장하는 것이 특징.

 

인접 리스트를 임의의 시작점에서 DFS로 순회하며(순서가 없는 그래프이므로 어디서 시작해도 상관없다.)방문 배열에 지나간 노드를 TRUE로 저장한다.또 그 다음 시작점을 정해 DFS 순회를 돌고, 방문 배열에 지나가지 않은 노드는 TRUE 표시, 이미 지나간 배열은 return으로 넘어가는 과정을 반복해준다.방문 배열에 방문하지 않은 배열이 없을 때까지 DFS 순회 반복....최종적으로 모든 노드를 방문하게 되어 ALL TRUE가 되면총 DFS가 몇번 일어났는지 카운트하여 출력하고 마무리...!