[백준] 11724번: 연결 요소의 개수 - JAVA

🔗 문제 링크

BOJ 11724번: 연결 요소의 개수

11724번: 연결 요소의 개수

 

📝 풀이 과정

BFS와 DFS 모두 풀이가 가능하지만 DFS로 문제를 풀어보았다.

 

반복문을 돌며, 만약 방문한 요소가 아닐 경우 해당 칸을 시작으로 하여 DFS를 시작한다. 방문하며 visit을 true로 변경하여 다시 방문하지 않도록 방문처리를 해주고 해당 요소에 연결되어 있고 방문하지 않았다면 재귀를 통해 DFS를 돌린다.
더이상 방문할 요소가 없어 DFS가 종료되면 연결 요소의 값을 하나 증가시킨다.

 

💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt();

        boolean[][] adj = new boolean[N + 1][N + 1];
        for (int i = 0; i < M; i++) {
            int n1 = sc.nextInt(), n2 = sc.nextInt();

            adj[n1][n2] = adj[n2][n1] = true;
        }

        boolean[] visit = new boolean[N + 1];
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            if (!visit[i]) {
                dfs(i, N, adj, visit);
                ans++;
            }
        }

        System.out.println(ans);

    }

    static void dfs(int n, int N, boolean[][] adj, boolean[] visit) {
        visit[n] = true;

        for (int i = 1; i <= N; i++) {
            if (!visit[i] && adj[i][n])
                dfs(i, N, adj, visit);
        }
    }
}

 

📊 제출 결과