유니온 파인드(Disjoint-set) 이란?

유니온 파인드(Union Find)란? 서로소 집합 자료구조(Disjoint-set)이라는 알고리즘으로도 불리며, 서로 다른 부분집합 간의 병합(Union) 과정을 의미한다. 

유니온 파인드는 서로 다른 집합을 합치거나, 한 집합이 다른 집합에 속해있는지를 확인하는 연산 두 가지로 이루어져있는데, 전자를 Union 이라하며, 후자를 Find라고 한다. 참고로 유니온 파인드는 집합이지만 트리로 생각하여 푸는 건데, 아래에서 설명하겠다.

1. 초기화 : 유니온 파인드는 우선 처음에 자기 자신을 루트라고 정하고 시작한다.

for (int i = 0; i <= n; i++) {
        p[i] = i;
    }

 

2. Union :  Union(x,y)는 y가 속한 집합을 x가 속한 집합에 포함시키는 함수이다.

 

최초의 집합

위 그림은 {1},{2},{3},{4},{5}를 표현한 그림이다. 각 집합은 어떠한 상관관계도 보이지 않는다.

 

1) Union(1,2)

Union(1,2)

2를 1에 포함시켰더니 위 그림과 같이 2가 1 밑에 붙는것을 알 수 있다.

이때 2의 루트는 1이 된다.(Parent[2] = 1)

 

2)Union(3,4)

Unoin(3,4)

Union(1,2)의 과정과 동일하다.(Parent[4] = 3)

 

3)Union(4,5)

Union(4,5)

위와 동일하게 붙는다. -> 현재 부분집합 = {1,2}, {3,4,5}

 

그렇다면 2개 이상의 부분집합끼리도 붙일 수 있을까?

4)Union(2,5)

Union(2,5)

어라? 분명 {3,4,5}를 {1,2}로 붙였는데 "5"만 움직여 붙어버리는 것을 볼 수 있다!(Parent[5] = 2)

이런 경우를 방지하기 위해 Find 함수를 사용한다.

 

3. Find : Find는 그 루트가 무엇인지? 찾는 함수이다.

루트는 부모노드들의 부모노드, 즉 맨 위 노드를 말하기 때문에 재귀함수 호출을 이용하여 구현 가능하다.

int find(int x){
 
    if(Parent[x] == x) return x;
 
    return find(Parent[x]);
 
}

 

그렇다면 Find를 이용하여 다시 Union으로 넘어가보자.

 

Union(4,5)

아까 이 상황에서 똑같이 Union(2,5)를 시도해보자.

find(5)를 하면 5의 루트 3이 반환되고, find(2)를 하면 2의 루트 1이 반환된다.

Union은 사실 루트끼리 붙여버리는 것이다.

따라서,

Union(2,5)

이렇게 같은 집합이 되는 것을 확인할 수 있다.

이 과정을 다시 코드로 보면,

 

int find(int x) { //루트 찾기
    if (p[x] == x) return x;
    return p[x] = find(p[x]);
}
 
void uni(int x, int y) {
    x = find(x);
    y = find(y);
    p[y] = x;
}

이렇게 되는데 사실 이것도 문제점이 하나 있다.

 

비엔나 소시지

바로 이렇게 줄줄이 소시지 모양으로 트리가 형성될 수 있는데, 다른 집합이랑 붙일 때 5를 붙이게 되면 n번만큼의 find를 해야하기 때문에 시간복잡도가 O(N)으로 증가하게 된다. 따라서,

이런식으로 붙이는 게 중요한데, 이는 Find 함수 내에서 루트를 계속 바꿔가면서 구현 가능하다.

int find(int x) { //루트 찾기
    if (p[x] == x) return x;
    return p[x] = find(p[x]);
}

이런식으로 반환 시 p[X]를 주기적으로 부모의 P값과 바꿔주면,

같은 부분 집합에 속한 원소들의 P[X]값은 모두 동일하게 되며, find 시 한번에 끝낼 수 있다. --> O(1)

 

따라서 유니온 파인드 알고리즘의 시간복잡도는

• find : O(1)
• Union : O(N)

이며, 서로 같은 부분집합인지 확인하는 부분도 find로 해결가능하므로 O(1)에 풀 수 있다.