BOJ 11724 - 연결 요소의 개수 (C++) / Union-Find 정리

문제를 푼 날짜: 2023. 12. 03

#graphs #graph_traversal #bfs #dfs

코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[1002];

void Union(int i, int j);
int Find(int i);

int main()
{
    int N, M;
    int a, b;
    int cnt = 0;
    cin >> N >> M;
    
    for(int i = 1; i <= N; i++){
        arr[i] = -1;
    }
    
    for(int i = 0; i < M; i++){
        cin >> a >> b;
        Union(a, b);
    }
    
    for(int i = 1; i <= N; i++){
        if(arr[i] == -1) cnt++;
    }
    cout << cnt;
    return 0;
}

void Union(int i, int j){
    int root1, root2;
    root1 = Find(i);
    root2 = Find(j);
    if(root1 != root2){
        arr[root2] = root1;
    }
}

int Find(int i){
    if(arr[i] == -1) return i;
    else return Find(arr[i]);
}

아이디어

주어진 예제 1을 시각적으로 표현하면, 아래 그림과 같이 1, 2, 5가 서로 연결되어 하나의 그룹을 형성하고, 3, 4, 6이 또 다른 그룹을 형성하는 것을 알 수 있다.

우리는 '총 몇 개의 그룹이 있는가?'에만 관심이 있으므로 계층(hierarchy)이 없는 기존의 그래프를 변형하여 다음과 같이 만들어줄 수 있다.

그래프의 각 정점을 그룹의 일원으로 보고, 그룹을 대표하는 루트(root)를 정해 각 정점이 어느 그룹에 속하는지 추적한다.

문제풀이 알고리즘

1. 초기화: 모든 정점을 초기화하여 자신이 속한 그룹의 루트를 가리키게 한다. 초기에는 모든 정점이 자신의 루트이므로, arr[] 배열을 -1로 초기화한다.
2. Union-Find 연산:

• Union 연산: 두 정점을 연결하는 간선을 입력받을 때마다, 두 정점이 속한 그룹을 하나로 합친다. 이는 한 그룹의 루트를 다른 그룹의 루트에 연결함으로써 이루어진다.
• Find 연산: 각 정점이 속한 그룹의 루트를 찾는다.

3. 연결 요소 개수 세기: 모든 간선 정보를 처리한 후, 각 정점의 루트가 -1인지를 확인하여 연결 요소의 개수를 센다. 루트의 개수가 곧 그룹의 개수가 된다.

Union-Find

Pseudocode

Union (i, j) //i와 j가 속한 두 트리를 병합
    root1 = Find(i);
    root2 = Find(j);
    if(root1 != root2) Parent[root2] = root1;
    
Find(i) // i가 속한 트리의 루트를 반환
	if(Parent[i] == null) return i;
    else return Find(Parent[i]);

Optimization

• Union-by-size : Union을 할 때 더 작은 트리가 더 큰 트리에 병합되도록 한다.
• Path Compression : Find(i)를 할 때 i에서 root(i)로 가는 경로에 있는 모든 원소가 root(i)의 direct child가 되도록 한다.

두 가지의 방법을 통해 트리의 높이가 더 낮아지고 시간복잡도를 낮출 수 있다.
위의 문제풀이에는 Path Compression을 활용했다.