27. Union Find

Union-Find 알고리즘이란?

집합을 표현하는 데 사용되며 서로소 집합을 구현하는 데 사용한다.

원소 간의 관계를 유지하면서 Union과 Find 연산을 효율적으로 수행하는 알고리즘이다.

 

그럼 C언어에서 집합을 어떻게 표현하게 될까?

어쩌면 집합보다는 트리의 표현이라고 생각된다.

표현 방법은 인덱스 번호를 값이라고 할 때 배열에 해당 인덱스에 저장된 값에 따라 달라진다.

만약 저장된 값이 -1이라고 하면 해당 집합은 루트 집합이다.

저장된 값이 -1이 아니라면 해당 인덱스를 부모로 하고 있는 자식 집합이다.

즉, -1이 루트, 아니라면 자식 집합이라는 뜻이다 (이런 표현 때문에 트리의 표현이라고 생각된다.)

 

예를 들어 a[5] = {-1, -1, -1, -1, -1}이라면 {0}, {1}, {2}, {3}, {4}라는 집합의 표현이 되는 것이며,

a[5] = {-1, 0, 1, -1, -1}이라면 {0, 1, 2}, {3}, {4}라는 집합의 표현이 된다.

---

Simple Union Find 연산

Union 연산은 두 집합을 합치는 연산, Find 연산은 해당 집합에서 루트 집합을 찾는 연산이다.

코드는 아래와 같이 단순하다.

int Simple_Find(int i){
    for(; parent[i] >= 0; i = parent[i]);
    return i;
}

void Simple_Union(int i, int j){
    parent[i] = j;
}

Simple Find연산은 i 값이 포함된 집합에서 -1 값을 가진 루트 집합이 무엇인지 찾는 연산이다.

Simple Union연산은 i 집합을 j 집합에 포함하는 연산이다.

parent[5] = {-1, -1, -1, -1, -1} 로된 집합이 있다고 하다면,

Simple_Union(1, 0); Simple_Union(2, 1);라고 한다면,

위의 예시 에서 들었던 parent[5] = {-1, 0, 1, -1, -1}로 변하게 된다.

---

WeightedUnion CollapsingFind 연산

Simple Union과 Simple Find 연산을 최적화 한 알고리즘이 Weighted Union과 Collapsing Find이다.

 

해당 알고리즘을 사용하기 전에 집합 표현 방법을 변경한다.

모든 루트 집합은 가중치를 가지며, 가중치는 음수값으로 나타낸다.

 

Weighted Union은 가중치를 비교하여 가중치가 더 큰 쪽으로 집합을 포함시키게 된다.

void Weighted_Union(int i, int j){
    int temp = (-parent[i]) + (-parent[j]);
    
    if(parent[i] > parent[j]){
        parent[i] = j;
        parent[j] = temp;
    }
    else {
        parent[j] = i;
        parent[i] = temp;
    }
}

 

Collapsing Find는 찾으려는 값의 루트 집합을 찾는 것이다. 하지만 해당 집합부터 루트 집합 이전에 존재하는 모든 노드를 루트에 직접 연결하게 된다.

예를 들면 a[7] = {-1, 0, 1, 2, 3, -1, -1}이 있다고 하자, 해당 집합은 {0, 1, 2, 3, 4}, {5}, {6}이다. 하지만 4의 루트를 찾기 위해서는 여러 단계를 거쳐야 한다. 이를 해결하기 위해 Find 연산 수행 시 루트까지 가는 경로상에 있는 모든 집합을 루트에 직접 연결하게 된다. 즉, Find 연산 이후 배열은 {-1, 0, 0, 0, 0, -1, -1}이 된다. 그러면 다음번에 Find 수행 시 조금 더 빠르게 루트 집합을 찾을 수 있게 된다.

int CollapsingFind(int i){
    int root, trail, lead;
    for(root = i; parent[root] >= 0; root = parent[root]);
    for(trail = i; trail != root; trail = lead){
        lead = parent[trail];
        parent[trail] = root;
    }
    return root;
}