연결 요소의 개수

문제

풀이

import java.util.Scanner;

// 연결 요소의 개수 - S2
public class ex11724 {

    static int n; // 정점의 개수
    static int m; // 간선의 개수
    static int[][] graph;
    static boolean[] ch;
    static int cnt=0;

    public static void DFS(int v){
        if(ch[v]==true) return; // 밑에 for 문에 의해 계속 같은 곳 방문 가능성 때문에
        else{
            ch[v]=true;
            for(int i=1; i<=n; i++){
                if(graph[v][i]==1){
                    DFS(i);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        graph = new int[n+1][n+1];
        ch = new boolean[n+1];

        for(int i=0; i<m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a][b] = 1;
            graph[b][a] = 1;
        }
        
        for(int i=1; i<=n; i++){
            if(!ch[i]) {
                DFS(i);
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

무방향 그래프에서의 연결된 요소의 개수를 구하는 문제이다. 한 그래프를 네트워크 연결이라고 치면, 연결되어있는 네트워크의 개수를 구하는 문제라고보면된다.

무방향 그래프 특성상 입력받은 간선을 1로 표시할때 반대로도 1을 표시해줘야한다.
그거 말고는 어려운 점이없었다.

[ 핵심 : 기억하자 ]
근데 한가지 걸리는 점이있었는데 , 애초에 main함수에서 DFS()를 호출할때 ch체크배열을 체크하고 들어갔기 때문에 DFS()에서는 체크 안해도 된다고 생각했다. 그런데 계속 정답 값이 안나와서 알아보니, DFS 내에서 for문이 돌아갈때 1~n까지 라서 방문 했던 정점을 계속 방문 하는 현상이 발생한다. 그래서 DFS내에서 자체적으로 ch 방문체크를 한번 더 해줘야 한다.