[136] 서로소 집합(Disjoint set)과 유니온 파인드(Union-Find)

1. 서로소 집합(Disjoint set)

그림과 같이 공통 원소가 없는 두 집합을 서로소 집합 또는 분리 집합이라고 합니다.

https://ko.wikipedia.org/wiki/서로소_집합

서로소 집합 - 위키백과, 우리 모두의 백과사전

이 서로소 집합을 자료구조로 나타내는 방법은 다양합니다.

그 중 그래프를 이용하면 다음과 같이 나타낼 수 있습니다.(한 집합 내에 원소들이 연결만 되어 있으면 됩니다.)

만약 1이 속해 있는 집합과 5가 속해 있는 집합이 서로소 집합인지 알기 위해서는, 1이 포함된 그래프에서 DFS나 BFS를 사용해서 5가 연결 되어있는지 확인하면 됩니다.

하지만 2와 5 또는 3과 6 등등 계속해서 두 원소가 속한 집합이 서로소 집합인지 확인하기 위해서는 더 효율적인 다른 방법이 필요합니다.

2. 유니온 파인드(Union-Find)

위에서 살펴본 문제를 해결하기 위해 서로소 집합을 나타내는 새로운 자료구조가 필요합니다.

위에서 만든 그래프를 트리로 바꾸었습니다.(역시 연결만 되어 있다면 구조는 상관 없습니다.)

트리로 바뀌면서 가장 큰 특징은 root를 활용할 수 있다는 것입니다.

어떤 두 원소가 속한 집합이 서로소 집합인지 확인하기 위해서는 두 원소의 root가 같은지만 확인하면 됩니다.(다르면 서로소 집합)

이제는 계속해서 확인하더라도 효율적으로 확인할 수 있습니다.

 

그리고 이렇게 만들면 좋은 점이 한 가지 더 있습니다.

바로 서로소 집합인 두 집합을 합하기(합집합)가 쉽습니다.

위 그림과 같이 두 트리 중 하나의 root를 다른 하나의 root에 자식으로 연결하기만 하면 끝입니다.

이제는 어떤 원소에서 root를 찾더라도 같은 root가 나오기 때문에 한 집합으로 표현할 수 있습니다.

 

이를 유니온 파인드 자료구조라고 부르며,

위에서 살펴본 것 처럼 두 집합을 합하는 기능을 유니온(Union), root를 찾는 기능을 파인드(Find)라고 하기 때문에 이런 이름이 붙었습니다.

https://ko.wikipedia.org/wiki/서로소_집합_자료_구조

서로소 집합 자료 구조 - 위키백과, 우리 모두의 백과사전

가. 파인드 최적화

위에서 본 것처럼 어떤 원소에 대해 파인드(Find)를 하면 그 원소가 속한 집합의 대표 원소(root)를 찾아 출력해줍니다.

다만, 트리 구조가 사향 트리(한 쪽으로 편향된 트리)라고 하면 최악의 경우 그 집합 전체를 찾아야 root를 알 수 있으므로, DFS나 BFS와 다를 게 없습니다.

따라서 경로 최적화 혹은 경로 압축(path compression)을 통해 파인드를 실행할 때마다 트리 구조를 평평하게 만들어줍니다.

위 그림처럼 예를 들어 3을 파인드했을 때, root를 찾기 위해 재귀적으로 부모 노드들을 지나갑니다.

이후에 이 길을 또 지나는 일은 비효율적이므로 지나간 부모 노드들을 모두 root의 자식으로 만들어줍니다.

이제 이 노드 중에 하나를 다시 파인드한다면 단 한 번만에 root를 찾을 수 있습니다.

나. 유니온 최적화

유니온을 할 때에도 최적화를 할 수 있습니다.

합하고 싶은 두 집합의 길이에 따라 효율성이 달라지기 때문입니다.

위 그림과 같이 높이가 높은 트리를 더 낮은 트리에 붙일 경우, 그 반대 경우보다 결과가 더 높아지므로 비효율적입니다.(유니온을 하면 할 수록 계속 높아집니다.)

따라서 트리의 높이(rank)를 기억해두고, 더 높은 트리에 더 낮은 트리를 붙입니다.

 

rank 값은 파인드할 때 경로 최적화를 통해 높이가 줄어들 수 있지만 업데이트 되지 않습니다.

다만 rank 값의 초기값은 0이고, rank 값이 같은 두 집합을 유니온할 때 rank가 1씩 증가합니다.

이렇게 되면 rank 값이 r인 어떤 집합의 원소 개수는 최소 \(2^{r}\)개가 보장되므로, 파인드의 수행 시간이 최악의 경우에도 \(O(\log_{n})\)이 보장됩니다.

다. 유니온 파인드 파이썬 코드

parent = [0, 1, 2, 3, 4, 5]
rank = [0, 0, 0, 0, 0, 0]

def find(u):
    if u != parent[u]:
        parent[u] = find(parent[u])
    return parent[u]

def union(u, v):
    u, v = find(u), find(v)
    if u != v:
        if rank[u] < rank[v]:
            parent[u] = v
            return
        if rank[u] == rank[v]:
            rank[u] += 1
        parent[v] = u

3. 마무리

유니온 파인드의 수행 시간을 구하는 것은 파인드를 할 때마다 최적화가 진행되므로 구하기 쉽지 않습니다.

하지만 굉장히 효율적이기 때문에 현실적인 입력에서 상수 시간 내에 동작한다고 합니다.

 

유니온 파인드는 이렇게 혼자서도 쓰이지만, 이후에 크루스칼 알고리즘을 통해 최소 신장 트리를 구하는 데 사용된다고 합니다.