[Algorithm] Union-Find 알고리즘 (Disjoint Set)

Disjoint Set(서로소 집합)은 서로 겹치는 요소가 없는 집합들을 저장하고 관리하는 자료구조.

• 주로 Union-Find 알고리즘을 사용하여 구현하며, 아래와 같은 작업들을 지원
  1. Union(합집합 연산): 두 개의 서로소 집합을 하나의 집합으로 합친다.
  2. Find(대표자 찾기 연산): 특정 원소가 속한 집합의 대표자를 찾는다.
  3. 같은 집합 여부 확인: 두 원소가 같은 집합에 속해 있는지 확인한다. (대표자가 동일한지 확인)

---

예제

사람들 간의 친구 관계를 관리하는 시스템

• 새로운 친구 관계 추가: x가 y의 친구가 된다. (집합에 새로운 요소 추가)
• 특정 두 사람이 직접적 또는 간접적으로 친구인지 확인한다.

예시

a, b, c, d, e, f, g, h, i, j 총 10명의 사람이 있다고 가정한다.

 

다음과 같은 친구 관계를 추가한다 :

• a <-> b, b <-> d, c <-> f, c <-> i, j <-> e, g <-> j

결과적으로 다음과 같은 그룹(집합)이 생성된다:

• G1 = {a, b, d}
• G2 = {c, f, i}
• G3 = {e, g, j}
• G4 = {h}

x와 y가 같은 그룹인지 여부를 확인한다. (x와 y가 직/간접적으로 연결된 친구인지 확인한다.)

• Disjoint set 해결 방법?
  
  • 처음에는 모든 사람들이 각자 다른 그룹에 속한다. 주어진 관계에 따라 그룹의 대표 멤버를 선정한다.
• 2명이 같은 그룹에 있는지 확인하는 방법?
  • 2명의 그룹 대표가 동일하다면 이 두 명은 친구

---

Disjoint Set 구조 및 주요 연산

Disjoint Set은 배열(Array)과 트리(Tree)를 사용하여 구현

1. Array 구조
   • 각 원소의 부모를 나타내는 Parent[] 배열을 사용한다.
   • 예를 들어, Parent[i] = j이면 i의 부모가 j
2. Tree 구조
   • 서로소 집합은 트리로 표현되며, 트리의 루트 노드가 집합의 대표이다.
   • i가 집합의 대표인 경우, Parent[i] = i
   • i가 집합의 대표가 아닌 경우, 대표를 찾을 때까지 트리를 따라 올라가면 찾을 수 있다.

---

Union-Find의 주요 연산

1. Find 연산:
   특정 원소가 속한 집합의 대표자를 찾는 연산
   • 루트 노드(자기 자신이 부모인 노드)를 반환한다.
   • 구현: 재귀적으로 Parent 배열을 탐색한다.
2. Union 연산:
   두 집합을 하나로 합치는 연산
   • 두 집합의 대표자를 찾은 뒤, 하나의 트리를 다른 트리 아래에 연결한다.
   • 경우에 따라 Union By Rank나 Path Compression으로 최적화한다.

class UnionFind:
    def __init__(self, size):
        # 초기화: 각 원소가 자기 자신을 부모로 가짐
        self.parent = list(range(size))

    def find(self, i):
        # 루트를 찾는 함수
        if self.parent[i] == i:  # i가 자신의 부모라면(루트 노드라면)
            return i
        # 재귀적으로 루트를 찾아가며 경로 압축 적용
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        # 두 집합을 합치는 함수
        root_i = self.find(i)
        root_j = self.find(j)

        if root_i != root_j:
            # 한 트리를 다른 트리 아래에 연결
            self.parent[root_i] = root_j

# 사용 예시
uf = UnionFind(10)  # 10개의 원소 초기화
uf.union(0, 1)      # 0과 1을 합침
uf.union(1, 3)      # 1과 3을 합침
uf.union(2, 4)      # 2와 4를 합침

# 0과 3이 같은 집합에 속하는지 확인
print(uf.find(0) == uf.find(3))  # True
# 2와 3이 같은 집합에 속하는지 확인
print(uf.find(2) == uf.find(3))  # False

---

최적화 방법

1. 경로 압축(Path Compression)

• Find 연산 최적화: 트리의 높이를 줄여 모든 원소가 루트에 직접 연결되도록 한다.
• 효과: Find 연산의 시간 복잡도를 거의 상수 시간으로 줄임.
• 코드 수정: self.parent[x] = self.find(self.parent[x])를 추가.

2. 랭크 기반 합치기(Union by Rank)

• Union 연산 최적화: 트리의 높이가 더 낮은 트리를 더 높은 트리 아래에 연결하여 트리의 높이를 최소화.
• 효과: 트리의 불균형을 방지하고 효율성 개선.

class DisjointSet:
    def __init__(self, n):
        self.parent = list(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:
            # 랭크 비교 후 트리 합치기
            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

# 사용 예시
ds = DisjointSet(10)
ds.union(0, 1)
ds.union(2, 3)
ds.union(1, 3)

print(ds.find(0) == ds.find(2))  # True
print(ds.find(0) == ds.find(4))  # False

---

시간 복잡도 / 공간 복잡도

1. 시간 복잡도
   • 기본 Union-Find: O(N)
   • 최적화(경로 압축 + 랭크 기반 합치기): O(α(N))  * α(N)은 역 아커만 함수.
2. 공간 복잡도
   • O(N): 각 원소의 부모 및 랭크를 저장.

---

요약

• Disjoint Set은 서로소 집합 관리를 위한 자료구조로, 주로 Union-Find 알고리즘으로 구현
• Find 연산: 특정 원소가 속한 집합의 대표자를 찾음.
• Union 연산: 두 집합을 하나로 합침.
• 최적화: 경로 압축과 랭크 기반 합치기를 사용하여 효율성 향상.

 

 

---

 

참고

https://www.geeksforgeeks.org/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/