Union Find(합집합 찾기)

서로소 집합 자료구조 중 하나로 무향 그래프의 연결된 요소들을 추적할 수 있다.(by 위키백과)

위키에 있는 의사코드를 보면 상당히 간단하게 구현이 가능하다.

 function MakeSet(x)
     x.parent := x

 function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot

위 모양은 단순한 형태로 구현한 것이다.

위 코드에서 문제점이 있는데 사향 이진 트리와 같은 모양으로 구성되면 매우 비효율 적이다.

그렇기 때문에 Find(x)함수에서 약간의 처리를 해주면 된다.

 function Find(x)
     if x.parent != x
        x.parent := Find(x.parent)
     return x.parent

흔히 경로 압축이라고 부르는 방법으로 파인트 연산을 수행 할 때마다 트리의 구조를 평평하게 만들는 방법이다.

위와 같은 모양을 아래와 같이 바꿔준다.

/*Union Find 구현*/
#include <iostream>
#define SIZE 10
using namespace std;
 
int parent[SIZE + 1];
 
void set_() {
    for (int i = 1; i <= SIZE; i++) parent[i] = i;
}
 
int find(int target) {
    if (target == parent[target]) return target;
    else return parent[target] = find(parent[target]);
}
 
void Union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a;
}
 
void PRINT_() {
    for (int i = 1; i <= SIZE; i++) {
        cout << i << ' ';
    }
    cout << '\n';
    for (int i = 1; i <= SIZE; i++) {
        cout << parent[i] << ' ';
    }
    cout << '\n' << '\n';
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    set_();
    cout << "초기값" << '\n';
    PRINT_();
    cout << "(1,7 Union)" << '\n'; Union(1, 7);
    PRINT_();
    cout << "(7,2 Union)" << '\n'; Union(7, 2);
    PRINT_();
    cout << "(9,2 Union)" << '\n'; Union(9, 2);
    PRINT_();
    for (int i = 1; i <= SIZE; i++)find(i);
    cout << "최종적으로 경로 압축" << '\n';
    PRINT_();
    return 0;
}