[AL] 6. Union-Find 알고리즘

 

6. Union-Find 알고리즘

1. Union-Find
2. Union-Find 구현
3. 최적화 (Optimization)

 

1. Union-Find

1.1. Union-Find 란?

서로소 집합(Disjoint Set) 라고 불리며, Union(x,y) 과 Find(x) 연산을 수행한다

Union(x,y) 를 수행하면 x와 y는 같은 집합에 속하게 되며, Find(x) 와 Find(y) 는 x, y 가 같은 집합에 속할 때만 같은 값을 가진다. 따라서, 전체 요소들을 서서히 묶어나가는 상황에서 유용하게 사용할 수 있는 자료구조이다.

 

1.2. 원리

• 배열을 이용해서 Tree 자료구조를 만들어 구현하며, 최상단 노드를 Root 노드로 하여 집합을 구분한다
• 주어진 두 원소 또는 집합을 합하는 Union 부분과 원소가 어떤 집합에 있는지 찾는 Find 부분으로 이루어져있다
• parent[i] : 원소 i 의 부모 노드를 가지고 있는 배열, 즉 parent[i] 는 i 의 부모노드
• (1,2) (2,5) (5,6) (5,8) (3,4) 수행 시, 아래와 같은 결과를 보인다

 

 

2. Union-Find 구현

2.1. 초기화

N 개의 원소가 각각의 집합에 포함되어 있도록 초기화 한다

void Set(){
    for(int i=1; i<=SIZE; i++){
        parent[i] = i;
    }
}

 

2.2. Union

두 원소 u, v 가 주어질 때, 이들이 속한 두 집합을 하나로 합친다

// u와 v의 원소가 들어오면 각각의 Root 노드를 찾아주고
// 두 root노드가 같지 않다면, u의 root 노드를 v로 설정해준다
void Union(int u,int v){
    
    u = Find(u);
    v = Find(v);
    
    // root가 같다면 이미 같은 트리
    if(u == v) return;
  
    // u의 루트가 v가 되도록
    parent[u] = v;
}

 

2.3. Find

어떤 원소 u 가 주어질 때, 이 원소가 속한 집합의 Root 를 반환한다

int Find(int u){
    
    // Root인 경우 x를 반환
    if(parent[u] == u){
        return u;
    }
    
    // 아니면 Root를 찾아감
    return parent[u] = Find(parent[u]);
}

 

 

3. 최적화 (Optimization)

이와 같이 트리로 구현하는 방법에는 큰 문제점이 발생할 수 있다.

바로 최악의 경우 완전히 비대칭적인 트리, 즉 연결 리스트 형태가 될 수 있다는 것이다. 만약 트리의 모양이 일자로 나온다면 Union 연산과 Find 연산의 수행시간이 O(N) 이 되버려 배열로 구현했을 때 보다도 효율이 나빠지게 된다.

이 문제는 두 트리를 합칠 때, 항상 높이가 더 낮은 트리를 높은 트리 밑에 넣음 으로서 해결이 가능하다. 이렇게 되면 트리의 높이가 크게 높아지는 현상을 방지할 수 있다. 이러한 최적화를 union-by-rank 라 하며, 여기서 rank 는 해당 트리의 높이를 저장한다.

 

시간 복잡도

일단 트리로 압축시켰기 때문에 find 시간복잡도는 O(logN) 을 갖게된다

또한 union 도 find 의 지배를 받기에 O(logN) 을 갖게 된다

---

사실 실제 시간 복잡도는 O(𝛼(N)) 이라고 한다. 𝛼는 애커만 함수를 뜻하며 N이 2^65536 일때, 함수 값이 5가 된다. 따라서 그냥 상수로 봐도 무방하다.

 

3.1. 최적화 소스코드

#include <iostream>
using namespace std;

const int SIZE = 100;

int parent[SIZE+1];
int level[SIZE+1];

void Set(){
    for(int i=1; i<=SIZE; i++){
        parent[i] = i;
        level[i] = 1;
    }
}

int Find(int u){
    
    // Root인 경우 x를 반환
    if(parent[u] == u){
        return u;
    }
    
    // 아니면 Root를 찾아감
    return parent[u] = Find(parent[u]);
}

// u와 v의 원소가 들어오면 각각의 Root 노드를 찾아주고
// 두 root노드가 같지 않다면, u의 root 노드를 v로 설정해준다
void Union(int u,int v){
    
    u = Find(u);
    v = Find(v);
    
    // root가 같다면 이미 같은 트리
    if(u == v) return;
        
    // v에 더 큰 값을 배치시키기 위함
    if(level[u] > level[v])
        swap(u, v);
        
    // u의 루트가 v가 되도록
    parent[u] = v;
    
    // u와 v의 깊이가 같을 때 v의 깊이를 늘려준다
    if(level[u] == level[v])
        ++level[v];
}

 

 

 

---

참고 자료

• https://www.crocus.co.kr/683