[백준]11724- 연결요소의 개수 문제 풀이(Java,자바)

 

https://www.acmicpc.net/problem/11724

들어가며

연결요소가 뭔지 까먹어서 제대로 못 푼 문제이다..

 

코드

package solved.ac.class3;

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

public class 백준11724_연결요소의개수 {
    static int[][] arr;
    static boolean[] visited;
    static int n, m;
    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());
        arr = new int[n+1][n+1];
        visited = new boolean[n+1];

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            arr[x][y] = 1;
            arr[y][x] = 1;
        }

        int count =0;
        for (int i = 1; i <= n; i++){
            if (!visited[i]){
                bfs(i);
                count++;
            }
        }
        System.out.println(count);
    }

    static void bfs(int start){
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        while (!queue.isEmpty()){
            int num = queue.poll();
            for (int i = 1; i <= n; i++){
                if (arr[num][i] == 1 && !visited[i]){
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

풀이법

연결요소가 뭘까??

이름에서 어느 정도 유추가 가능한데 각 정점들이 서로 경로로 연결된 부분 그래프를 의미한다.

(1) --- (2)    (4) --- (5)
        |        
       (3)

 

위 그래프는 {1,2,3} 과 {4,5} 두 가지의 연결 요소를 가지고 있는 것이다.

 

그러면 이 연결요소를 어떻게 구할 수 있을까?

그래프 탐색 기법인 dfs, bfs 둘 중 아무거나를 사용한다.

그래프 탐색하는 동안 방문한 노드를 기록한다.

그러면 끝.

아주 간단하다.

 

        int count =0;
        for (int i = 1; i <= n; i++){
            if (!visited[i]){
                bfs(i);
                count++;
            }
        }
        System.out.println(count);

위 그래프에서 예시를 들어보면 다음과 같다.

만약 1에서 시작한다고 한다면 dfs든 bfs든 한 번 돌리면 자연스럽게 한 연결 요소 안을 다 돌게 된다.

1 -> 2 -> 3 이런 식으로 말이다.

그리고 2에서 시작하면 어떻게 될까??

1에서 시작할 때, 1,2,3을 방문했다고 표시했기 때문에 2에서 시작은 무시가 된다. 3도 마찬가지이다.

4가 되서야 새로운 탐색을 진행한다.

이렇게 두 개의 연결요소가 있다고 파악할 수 있다.