[백준] 11724번 연결요소의 개수 구하기 풀어보기 : Programming Story

1. 문제

1) 링크

www.acmicpc.net/problem/11724

2) 문제

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

3) 입력

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

4) 출력

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

더 자세한 문제의 제한사항을 보고 싶은 경우 위의 링크에 들어가서 확인해보자.

2. 풀이

이 문제는 연결요소(Connected Component) 의 개수를 구하는 문제이다.

만약 그래프가

위 그림과 같이 생겼다면 연결요소는 2개라고 할 수 있다. 서로 연결되어 있는 요소는 2개이며 연결요소가 2개 이상이라는 소리는 그래프가 끊겨 있다는 말과도 같다. 한 노드에서 시작하여 모든 노드를 다 순회할 수 없다는 말과 같다.

그렇다면 위 백준 문제는 이러한 연결요소가 몇개인지를 물어보는 문제인데 어떤 식으로 해결 할 수 있을까?

정답은 간단하다. 해당 노드가 사용되었는지 사용되지 않았는지를 저장하는 boolean 배열 c를 하나 만들고 전체 노드에 대해서 for문을 돌리는 것이다. 그러면서 해당 c 배열이 false인 경우 bfs 또는 dfs 함수를 호출하고 연결요소의 개수를 늘리는 것이다. 함수를 호출한 이후에도 해당 노드가 false라는 뜻은 전체를 순회했는데도 해당 노드가 사용되지 않았다는 것을 의미하므로 그래프가 끊어져있다는 것을 의미한다. 따라서 그럴 경우에 답의 개수를 증가시키면서 연결요소의 개수를 구할 수 있다.

위의 내용을 코드화시킨 것의 일부분은,

 for(int i=1; i<=n; i++){
            if (!c[i]){
                ans++;
                dfs(i);
            }
        }

위와 같다.

그리고 dfs 함수의 구현은

https://www.programmingstory.com/2024/02/1260-dfs-bfs.html

해당 포스트에서도 다루었듯이,

 public static void dfs(int x){
        if (c[x]) return;
        c[x]=true;
        for(int y: a[x]){
            if (!c[y]){
                dfs(y);
            }
        }
    }

이런식으로 구현할 수 있다.

위 내용을 모두 다 종합하여서 전체 코드를 작성해보면,

import java.util.*;


public class Main{
    static ArrayList<Integer>[] a;
    static boolean c[];
    public static void dfs(int x){
        if (c[x]) return;
        c[x]=true;
        for(int y: a[x]){
            if (!c[y]){
                dfs(y);
            }
        }
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        a=(ArrayList<Integer>[])new ArrayList[n+1];
        for(int i=1; i<=n; i++){
            a[i]=new ArrayList<Integer>();
        }
        c=new boolean[n+1];
        for(int i=0; i<m;i++){
            int from=sc.nextInt();
            int to=sc.nextInt();
            a[from].add(to);
            a[to].add(from);
        }
        int ans=0;
        for(int i=1; i<=n; i++){
            if (!c[i]){
                ans++;
                dfs(i);
            }
        }
        System.out.println(ans);
    }
}

위와 같이 작성할 수 있다.