[크래프톤 정글 ] Union-Find 자료 구조

Union-Find 자료 구조는 Disjoint Set(서로소 집합)이라고도 불리며, 집합 간의 합집합(Union)과 특정 원소가 속한 집합을 찾는(Find) 연산을 효과적으로 수행하기 위한 자료 구조다. 이 자료 구조는 주로 그래프 알고리즘에서 사이클을 판별하거나, 서로 연결된 컴포넌트를 찾는 데 사용된다.

기본 개념

1. 집합(sets): 각 원소는 하나의 집합에 속하며, 처음에는 모든 원소가 자신만을 포함하는 집합에 속하게 된다.
2. 합집합(Union): 두 집합을 하나의 집합으로 합친다.
3. 찾기(Find): 특정 원소가 속한 집합의 대표 원소(루트)를 찾는다.

주요 연산

Union-Find 자료 구조는 두 가지 기본 연산을 제공한다:

1. Find(x):

   • 원소 x가 속한 집합의 루트(대표 원소)를 찾는다.
   • 경로 압축(Path Compression) 기법을 통해 효율적으로 구현할 수 있다. 이 기법을 사용하면, Find 연산 중 만나는 모든 노드를 루트에 직접 연결하여 트리의 높이를 줄인다.

2. Union(x, y):

   • x가 속한 집합과 y가 속한 집합을 합친다.
   • Union by Rank(또는 Union by Size) 기법을 통해 트리의 높이를 줄일 수 있다. 이 기법에서는 높이가 낮은 트리를 높이가 높은 트리 밑에 연결하여 트리의 균형을 유지한다.

구현 예시

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size

    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):
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

# 사용 예시
uf = UnionFind(10)  # 크기가 10인 집합 생성

uf.union(1, 2)  # 1과 2를 하나의 집합으로 합침
uf.union(2, 3)  # 2와 3을 하나의 집합으로 합침 (즉, 1, 2, 3이 모두 같은 집합에 속함)
print(uf.find(1))  # 1이 속한 집합의 루트 출력 (1, 2, 3 중 하나가 출력될 것)
print(uf.find(3))  # 3이 속한 집합의 루트 출력 (1, 2, 3 중 하나가 출력될 것)

최적화 기법

1. 경로 압축(Path Compression): Find 연산을 최적화하는 방법으로, 재귀적으로 부모를 찾은 뒤에, 찾은 루트를 경로상의 모든 노드에 직접 연결한다. 이를 통해 트리의 높이를 줄여 나중에 Find 연산이 더 빠르게 수행된다.

2. Union by Rank: Union 연산을 최적화하는 방법으로, 집합을 합칠 때, 두 트리의 높이(rank)를 비교하여 높이가 낮은 트리를 높이가 높은 트리 밑에 두는 방식이다. 이렇게 하면 트리의 균형이 유지되어 최악의 경우에도 트리의 높이가 logN을 넘지 않게 된다.

시간 복잡도

Union-Find 자료 구조의 시간 복잡도는 경로 압축과 Union by Rank 최적화를 적용할 경우 거의 상수 시간에 가까운 O(α(N))이 된다. 여기서 α(N)은 아커만 함수의 역함수로, 매우 느리게 증가하기 때문에 실질적으로는 O(1)로 볼 수 있다.

활용 예시

Union-Find 자료 구조는 다음과 같은 문제에 자주 사용된다:

1. 최소 신장 트리(MST): 크루스칼 알고리즘(Kruskal's Algorithm)에서 간선 간의 연결 여부를 판별하는 데 사용된다.
2. 사이클 탐지: 무향 그래프에서 사이클이 존재하는지를 확인하는 데 사용된다.
3. 동적 연결성 문제: 네트워크에서 동적으로 연결된 컴포넌트를 관리하고, 두 노드가 같은 컴포넌트에 속하는지를 확인하는 데 사용된다.