DFS

import java.util.*;
 
 
//dfs 기본
public class Main {
    static int nV; //정점의 개수
    static int nE; //간선의 개수
    static boolean[] visit; //방문 배열
    static int[][] arr;
 
    static int dfs_count(){
        int component = 0;
        for(int i = 0; i < nV; i++){
            if(!visit[i]){
                System.out.println("new Node Start");
                dfs(i);
                component++;
            }
        }
        return component;
    }
 
    static void dfs(int n){
        visit[n] = true;
        System.out.println(n);
        for(int i = 0; i < nV; i++){
            if(visit[i] == false && arr[n][i] == 1 )
                dfs(i);
        }
    }
 
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
 
        nV = s.nextInt();
        nE = s.nextInt();
 
        arr = new int[nV][nV];
        visit = new boolean[nV];
 
        for(int i=0; i <nE; i++){
            int t1 = s.nextInt();
            int t2 = s.nextInt();
 
            arr[t1][t2] = arr[t2][t1] = 1;
        }
        int result = dfs_count  ();
        System.out.println("컴포넌트의 개수는:" + result);
 
    }
}
 
9
7
0 1
1 3
2 3
4 6
5 7
5 8
7 8
new Node Start
0
1
3
2
new Node Start
4
6
new Node Start
5
7
8
컴포넌트의 개수는: 3
 
 
 

컴포넌트의 개수는 노드가 다시 시작할 때의 총개수이다.

0-1-3-2와 4-6, 5-7-8 이렇게 총 9개의 노드가 이렇게 따로 분리되어 이루어져 있다.

만약 dfs 메소드만 존재했다면 0-1-3-2에서 dfs가 끊기게 된다.

그래서 dfs_count 메소드가 끊기지 않게 노드의 개수만큼 for문을 돌려, visit하지 않은 노드를 다시 dfs 돌리게 된다.

그래서 dfs함수가 끝나고 dfs_count가 0,1,2,3은 visit가 됐기 때문에, 4부터 다시 dfs를 돌린다. 그러고 나서, dfs_count가 들어갈 때마다 component 개수를 늘려주면 총 component의 개수를 알 수 있게 된다.