유니온 파인드(union-find)

union-find 란

Union-Find(유니온-파인드)는 분리집합(Disjoint Set) 자료구조를 구현하는 알고리즘입니다. 유니온-파인드는 서로소 집합(Disjoint Set)들을 효율적으로 관리하고 연산하는데 사용되며, 대표적으로 서로소 집합 MakeSet, Union 에서 find를 추가하여 세 가지 연산을 지원합니다.

Union-Find 알고리즘은 트리 구조를 활용하여 각 집합을 표현합니다. 각 원소는 트리의 노드를 나타내며, 집합의 대표 원소(루트 노드)를 통해 각 트리를 구분합니다. 이때, 트리의 높이가 너무 크면 Find 연산의 성능이 저하될 수 있으므로, 앞서 소개했던 경로 압축(Path compression)과 합치기 Union by rank등의 최적화 기법을 적용하여 효율적인 연산을 보장할 수 있습니다.

union-find 연산

• MakeSet(x): 원소 x를 자신만으로 구성된 새로운 집합으로 만듭니다. 이때, x 자체가 하나의 집합을 의미합니다.
• Union(x, y): 두 개의 원소 x와 y가 속한 집합을 하나로 합칩니다. 이때, 두 집합이 서로 겹치지 않아야 합니다. 즉, 합집합은 하나의 큰 집합이 됩니다. 이때, 두 집합 중 하나의 대표 원소(루트 노드)를 선택하여 다른 집합의 루트 노드에 연결하면 됩니다.
• Find(x): 원소 x가 속한 집합의 대표 원소(루트 노드)를 찾아서 반환합니다. Find 연산은 해당 원소가 어떤 집합에 속해 있는지를 알려주는 역할을 합니다.

union-find가 트리 구조로 만드는 이유

문득 조사하면서 그동안의 알고리즘들은 배열(array)를 활용하여서 만들었던 것 같은데 tree구조로 만드는 이유가 궁금해졌습니다.

찾아본 결과 Union-Find를 트리 구조로 만드는 이유는 연산의 효율성과 간결성을 높이기 위해서입니다. 트리 구조를 사용하면 Find와 Union 연산을 더 효율적으로 수행할 수 있기 때문입니다.

Find 연산의 효율성: 경로 압축(Path compression) 최적화를 적용하여 Find 연산 시에 경로 상의 노드들을 직접 루트 노드에 연결함으로써 트리의 높이를 줄일 수 있습니다. 이렇게 하면 Find 연산의 시간 복잡도를 평균적으로 거의 O(1)에 가깝게 단축시킬 수 있습니다.

Union 연산의 효율성: Union by rank 로 최적화를 적용하여 트리의 높이가 증가하지 않도록 하면, Union 연산의 시간 복잡도를 O(log n) 수준으로 유지할 수 있습니다.

코드로 구현

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 경로 압축
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return

        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

# 테스트
n = 10
uf = UnionFind(n)

uf.union(0, 1)
uf.union(2, 3)
uf.union(4, 5)
uf.union(0, 2)

print(uf.find(1))  # 출력: 3 (0과 1, 2, 3이 하나의 집합으로 합쳐졌으므로)
print(uf.find(4))  # 출력: 5 (4와 5가 하나의 집합으로 합쳐졌으므로)
print(uf.find(6))  # 출력: 6 (아직 별도의 집합으로 남아 있으므로)