[DFS] 백준 - 11724번: 연결 요소의 개수 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

 

문제는 위와 같다.
이 문제 또한 전 게시글과 똑같은 방식이었다.

[DFS] 프로그래머스 - 네트워크 문제 JAVA 풀이

따라서 같은 방식을 적용해보면

1. 메인 코드에서 노드들이 방문했는지를 체크하여 안 했을 경우 DFS를 돌리고 count++ 해준다.
2. 그렇게 돌리다 보면 서로 간선이 끊겨있는 노드들은 check 배열에서 false가 되어있을 것이다.
3. 그러면 그 노드들을 다시 DFS를 돌리고 count++을 해주면 된다.

 

코드

import java.util.Scanner;

public class Main {
    static int[][] nodes;
    static boolean[] check;
    static int m;
    static int n;

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

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

        nodes = new int[n][n];
        check = new boolean[n];

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            nodes[a][b] = 1;
            nodes[b][a] = 1;
        }

        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!check[i]) {
                dfs(i);
                count++;
            }
        }

        System.out.println(count);
    }

    private static void dfs(int start) {
        check[start] = true;

        for (int i = 0; i < n; i++) {
            if (nodes[start][i] == 1 && !check[i]) {
                dfs(i);
            }
        }
    }
}