문제

풀이

이해

그래프의 간선 정보를 입력받고 연결 요소의 개수를 세는 문제이다.

그래프는 모든 노드가 간선에 의해 연결될 필요가 없다. 연결 요소는 말 그대로 그래프에서 간선에 의해 연결된 노드 집합을 의미한다. 한 그래프에서는 연결 요소가 여러 개 존재할 수도 있다. 이 때, 보는 관점에 따라 다르지만 연결 요소 혹은 작은 그래프가 포함되어 있다고 할 수 있다.

접근

DFS로 한 연결 요소에 대한 모든 노드를 순회한다. 노드 순회가 끝나면 더 이상 연결된 노드가 없다는 것을 의미하므로 1개의 연결요소로 인정하여 카운트한다.

순회한 노드는 다시 방문할 필요가 없기 때문에 방문 여부를 따로 기록한다.

코드

package java_baekjoon;

import java.util.Arrays;
import java.util.Scanner;

public class prob11724{
    static int N;
    static int M;
    static int[][] tree;
    static boolean[] visited;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int ans = 0;
        N = sc.nextInt();
        M = sc.nextInt();

        tree = new int[N+1][N+1];

        for(int[] i:tree){
            Arrays.fill(i, 0);
        }
        
        visited = new boolean[N+1];

        for(int i=0;i<M;i++){
            int node1 = sc.nextInt();
            int node2 = sc.nextInt();

            tree[node1][node2] = 1;
            tree[node2][node1] = 1;
        }

        for(int i=1;i<=N;i++){
            if(!visited[i]){
                DFS(i);
                ans++;
            }
        }

        System.out.println(ans);

        sc.close();
        return;
    }

    public static void DFS(int node){
        visited[node] = true;

        for(int i=1;i<=N;i++){
            if(!visited[i] && tree[node][i] == 1){
                DFS(i);
            }
        }
        return;
    }
}

결과