합집합 찾기 - Union Find, 유니온 파인드 알고리즘

합집합 찾기 - Union Find

 노드들이 존재하고 있을 때 같은 집합에 있는가를 판별하는 알고리즘으로 Disjoint-set 자료구조를 사용하는 알고리즘입니다. 어느 곳에서는 Union Find를 자료구조로 보는 곳도 있지만 저는 알고리즘으로 보고 글을 작성하겠습니다.

 

 

Union Find의 연산

 

1. 초기화

 일단 트리의 개념을 사용하기 때문에 각 노드들의 부모를 자기 자신으로 초기화 해줘야 합니다. 

노드	1	2	...	N
부모	1	2	...	N

 초기화를 하면 부모 노드를 가리키는 배열이 위 처럼 초기화 됩니다.

 

2. Union (= Merge)

 두 트리를 합치는 역할을 합니다. 두 트리에 있는 노드들이 가리키는 부모를 통일해 같은 집합으로 넣어주는 연산입니다.

 위 표를 업데이트 해보면 아래와 같은 형태가 됩니다.

노드	1	2	...	N
부모	1	1	...	N

 이런식으로 Union에서는 부모를 변경해주는 연산을 해야 합니다.

 

 

3. Find

 노드의 부모를 찾아주는 연산입니다. 찾아가는 방법은 ' 해당 노드의 부모 찾기 -> 루트 노드가 아니면 부모의 부모 찾기 -> 계속 따라가 최종 부모를 찾기 ' 의 순서를 따라가게 됩니다.

 

 여기서 Find 연산은 재귀적인 연산이다보니 트리의 높에 영향을 많이 받게 됩니다. 만일 선형적인 트리의 경우 부모를 찾는데 O(N) 시간복잡도를 가지게 되어 적절한 트리 형태를 가지게 하는게 좋습니다.

이런 식의 모양이면 사실상 배열이다

 

코드로 보는 Union Find, 그리고 최적화

#include <iostream>
using namespace std;
int parent[1000001];

int FindParent(int x){
    if(x == parent[x])
        return x;

    return FindParent(parent[x]);
}

void Merge(int x, int y){
    x = FindParent(x);
    y = FindParent(y);

    if(x == y)
        return;
    else
        parent[x] = y;
}

int main(){
    for(int i = 0; i <= 1000000; i++)
        parent[i] = i;
}

 

 위 3개의 연산을 간단하게 옮겨본 코드입니다. C++ 에서는 union 연산자가 있다고 해서 Merge로 대체했습니다. 그런데 위 방식으로 하게 된다면 선형적인 트리가 만들었을 때 Find에서 시간복잡도가 O(N)이 되어버려 고민을 한 이유가 사라지게 됩니다. 때문에 아래와 같은 방식으로 Find를 변경하게 됩니다.

 

int FindParent(int x){
    if(x == parent[x])
        return x;

    return parent[x] = FindParent(parent[x]);
}

 

 Find를 하면서 부모를 찾아가는 과정에서 부모를 갱신해 줌으로서 시간 복잡도를 줄인 알고리즘입니다. 이를 통하면 O(a(N))의 시간 복잡도를 가지게 된다는데 a는 아커만 함수라고 합니다. N이 2^65536일때 함수의 결과값이 5가 나온다고 하니 사실상 대부분의 경우 상수의 시간복잡도를 가지게 되는, 아주 빠르다고 할 수 있습니다.

 

void Merge(int x, int y){
    x = FindParent(x);
    y = FindParent(y);

    if(x == y)
        return;

    if(level[x] > level[y])
        swap(x, y);

    else
        parent[x] = y;

    if(level[x] == level[y])
        level[y]++;
}

 

 Merge의 경우에도 트리의 깊이 개념을 넣어 더 최적화 할 수 있습니다. 기존의 Merge는 선형 리스트가 나올 수 있는 가능성이 있지만 개선된 알고리즘은 레벨 개념을 넣어 더 최적화 하는 것입니다. 그런데 Find의 개선된 버전에서 어느정도 최적화를 해 주기 때문에 level은 제외하고 풀이를 해도 괜찮습니다. 저도 위 최적화 방법은 알아만 두고 잘 쓰지는 않았네요.

 

 

풀이해보면 좋은 문제

1717번: 집합의 표현

- 풀이

백준 1717 집합의 표현 - C++, Union find

 위 개념만 알고 있어도 순수하게 풀 수 있는 문제입니다.