[알고리즘] 연결 요소의 개수(백준11724번)_실버2_dfs,bfs

문제링크

📝 문제

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

2

예제 입력 2

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

예제 출력 2

1

---

🔍 정답

dfs 풀이

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  

public class Main {  
    static int N, M;  
    static boolean[] visit;  
    static int[][] arr;  
    static int cnt;  

    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        N = Integer.parseInt(st.nextToken()); // 정점의 개수  
        M = Integer.parseInt(st.nextToken()); // 간선의 개수  

        visit = new boolean[N+1];  
        arr = new int[N+1][N+1];  

        /**  
         * 간선 입력받기  
         * 입력받은 값들을 1로 바꾸어준다!  
         */        
         for (int i = 0; i < M; i++) {  
            st = new StringTokenizer(br.readLine());  
            int a = Integer.parseInt(st.nextToken());  
            int b = Integer.parseInt(st.nextToken());  

            arr[a][b] = arr[b][a] = 1;  
        }  

        /**  
         * 1부터 N까지 방문하지 않은 곳이 있다면 카운팅 해주면서 dfs를 부른다.  
         */        
         for (int i = 1; i <= N; i++) {  
            if (!visit[i]) {  
                cnt++;  
                dfs(i);  
            }  
        }  
        System.out.println(cnt);  
    }  

    /**  
     * arr[1][i~N까지] 돌면서 연결요소라고 입력받은 값이 있으면 재귀함수를 부르게 된다.  
     * 만약 1 2, 2 5 가 연결요소라면, 카운팅 1을 하고 dfs(1)을 부른다.  
     * 처음에 visit[1] = true가 되고 for문을 통해 dfs(2)를 부르며 visit[2] = true, 그 다음은 dfs(5)를 불러서 visit[5] = true 가 된다.  
     * 더 이상 연결요소가 없다면 메인 함수로 돌아가서 for문을 진행하게 된다.  
     * 다음 for문 i = 2이지만 이미 i = 1 dfs 함수에서 visit[2] = true로 바꾸었으므로 dfs를 다시 부르지 않고 i = 3으로 넘어가며  
     * visit[3] = false 이므로 카운트 1을 더하고 dfs(3)을 불러서 3과 이어진 새로운 연결요소들을 탐색한다.  
     */    
     public static void dfs(int num) {  

        visit[num] = true;  

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

bfs 풀이

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.LinkedList;  
import java.util.Queue;  
import java.util.StringTokenizer;  

public class Main {  
    static int N, M;  
    static boolean[] visit;  
    static int[][] arr;  
    static int cnt;  

    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        N = Integer.parseInt(st.nextToken()); // 정점의 개수  
        M = Integer.parseInt(st.nextToken()); // 간선의 개수  

        visit = new boolean[N+1];  
        arr = new int[N+1][N+1];  

        /**  
         * 간선 입력받기  
         * 입력받은 값들을 1로 바꾸어준다!  
         */        
         for (int i = 0; i < M; i++) {  
            st = new StringTokenizer(br.readLine());  
            int a = Integer.parseInt(st.nextToken());  
            int b = Integer.parseInt(st.nextToken());  

            arr[a][b] = arr[b][a] = 1;  
        }  

        /**  
         * 1부터 N까지 방문하지 않은 곳이 있다면 카운팅 해주면서 bfs를 부른다.  
         */        
         for (int i = 1; i <= N; i++) {  
            if (!visit[i]) {  
                cnt++;  
                bfs(i);  
            }  
        }  
        System.out.println(cnt);  
    }  

    /**  
     * 1 2, 2 5, 3 4 를 연결요소라고 가정하면,  
     * 처음에 1을 Queue 에 넣어주고 visit[1] = true로 바꾸어준다.  
     * 그런 후 Queue가 빌 때까지 반복문을 돌아줄 것이다.  
     * arr[1][1~N까지] 중에 연결요쇼라고 입력받은 값이 나오면 Queue에 넣어준다.  
     * 처음에는 q = [1], visit[1] = true 가 되고 while문을 타면서 q = [2, 5], visit[2], visit[5] = true가 된다.  
     * 더이상 연결요소가 없다면(Queue가 빈다면) 메인 함수로 돌아가서 카운팅을 하고 for문을 진행한다.  
     * i = 2부터 다시 진행되지만 visit[2] = true이므로 i = 3으로 넘어가게 되고   
* if문을 타면서 카운팅과 함께 bfs함수를 부르며 새로운 연결요소를 탐색하게 된다!  
     */    
     public static void bfs(int num) {  
        Queue<Integer> q = new LinkedList<>();  
        q.offer(num);  
        visit[num] = true;  

        while (!q.isEmpty()) {  
            num = q.poll();  
            for (int i = 1; i <= N; i++) {  
                if (arr[num][i] == 1 && !visit[i]) {  
                    q.offer(i);  
                    visit[i] = true;  
                }  
            }  
        }  
    }  
}