[자료구조] 유니온-파인드(union-find)

유니온 파인드 = 디스조인트 셋(disjoint set) = 머지 파인드 셋(merge find set)

 

디스 조인트 셋은 서로소 집합(교집합이 공집합인 집합)

 

많은 상호 배타적 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.

 

A와 B 사건 중 둘이 동시에 일어날 수 없고 둘 중 하나만 일어나야 한다.

 = 두 사건 중 하나의 사건이 일어날 확률이 두 사건이 각각 일어날 단순 확률의 합 과 같다.

(P(A)가 일어날때 P(B)가 0이기 때문)

P(A or B) = P(A) + P(B)

 

//상호배타적이 아닌 독립적 관계는 A,B의 교집합이 없는 것은 동일하나 A,B동시에 일어나도 상관없음.

 

---

구현에는 Union, Find가 존재.

부분 집합들은 트리로 표현 할 수 있고, 파인드를 통해 루트 노드를 찾고, 유니온을 통해 트리를 합치게 된다.

 

-Find : 노드가 어떤 트리에 속하는지 찾는 연산. 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. 파인드는 일반적으로 어떤 원소가 속한 집합을 대표하는 원소를 반환하는데, 이를 위해서 어떤 원소와 각 대표 원소들 간의 Find결과를 비교해 같은 집합 여부를 판단한다.

-Union: 두 개의 집합을 하나의 집합으로 합친다.

 

초기에 각 노드는 자기 자신을 루트 노드로 가지고 있다.

parent = [0]*(n+1)
level = [0] + [1]*n

for i in range(1, n+1):
    parent[i] = i

 

Find를 통해 반환 되는 값은 그 집합의 대푯값(해당 트리(집합)의 루트노드)이다.

 

def Find(u):
    if ( u == parent[u] ):
        return u
    return parent[u] = Find(parent[u])

해당 노드는 루트 노드를 찾기 위해 부모값을 통해서 Find함수를 호출한다. 이동하며 모든 노드의 루트노드도 갱신한다.

 

Union은 Find를통해 두 개의 트리의 루트 노드를 이용해 하나의 트리로 합치게 된다.

def Union(u,v):
    u = Find(u)
    v = Find(v)
    
    if(u===v):
        return
        
    if (level[u] > level[v]:
        parent[u] = v
        level[u] += level[v]
    else:
        parent[v] = u
        level[v] += level[u]

u와 v 를 합치는 함수. 루트가 같다면 돌아가고 아니라면 한쪽 트리를 다른쪽에 이어준다(루트노드끼리)

(level이용 높이가 낮은 트리를 높은 트리 아래로 들어가게끔 설계)