백준 11724번 연결 요소의 개수 성공 자바 풀이

❓문제

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

 

---

🔠 입력

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

---

🖨️출력

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

---

✍️ 예제 입력

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

✔️ 예제 출력

2

✍️ 예제 입력

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

✔️ 예제 출력

1

---

💡해설

방문 체크 배열을 전부 false로 초기화하고 방문하지 않은 노드 발견할 때마다 체크 한 후 answer를 더해준다.

dfs를 돌려서 연결 요소의 모든 노드를 방문한다.

import java.util.Scanner;

public class Main {

    static int[][] treeArray;
    static boolean[] visited;
    static int answer = 0;

    public static void main(String[] args) {

        // 2개의 수를 받는다.
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // Node 
        int M = sc.nextInt(); // 간선


        treeArray = new int[N+1][N+1];
        // 방문 배열 초기화 
        visited = new boolean[N + 1];

        for(int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            treeArray[a][b] = 1;
            treeArray[b][a] = 1;

        }

        // dfs 
        for(int i = 1; i < N+1; i++) {
            // 방문 하지 않은 노드 방문시 
            if(visited[i] == false) {
                visited[i] = true;
                answer+=1; // 갯수 ++
                dfs(i);
            }
           
        }
        System.out.println(answer);

    }

    private static void dfs(int n) {
        // treeArray length는 노드 + 1 이다 
        for(int j = 1; j < treeArray.length; j++) {
            // n 노드와 연결된 노드 모두 방문한다. 
            if(visited[j] == false && treeArray[n][j] == 1) {
                visited[j] = true;
                dfs(j);
            }
        }
        
        
    }
}