디스조인트 셋 (Disjoint-Set)

디스조인트 셋은 서로 겹치지 않는(disjoint) 부분 집합들로 나누어진 요소들의 집합을 표현하고 조작하는 데이터 구조이다.
각 부분 집합은 대표 요소(representative)를 가지며, 이를 통해 집합을 식별한다.

특징

  1. 동적 집합 관리: 요소들을 동적으로 그룹화하고 관리할 수 있다.
  2. 빠른 연산: Union과 Find 연산을 매우 효율적으로 수행한다.
  3. 경로 압축과 랭크 최적화: 트리 구조를 최적화하여 성능을 향상시킨다.

장점

  1. 효율성: 거의 상수 시간에 가까운 연산 복잡도를 제공한다.
  2. 간단한 구현: 기본 개념이 직관적이고 구현이 비교적 간단하다.
  3. 메모리 효율성: 추가적인 데이터 구조 없이 요소들의 관계를 표현한다.

단점

  1. 제한된 기능: 주로 Union과 Find 연산에 특화되어 있어 다른 복잡한 연산은 지원하지 않는다.
  2. 초기 설정 비용: 모든 요소에 대해 초기 집합을 생성해야 한다.

응용

  1. Kruskal의 최소 신장 트리 알고리즘
  2. 사이클 검출 알고리즘
  3. 네트워크의 연결성 확인
  4. 이미지 세그멘테이션

동작 원리

디스조인트 셋은 트리 구조를 사용하여 집합을 표현한다.
각 트리의 루트 노드가 해당 집합의 대표 요소가 된다.

구성 요소

  1. 노드: 각 요소를 나타내며, 부모 노드에 대한 참조를 가진다.
  2. 트리: 같은 집합에 속한 요소들을 표현한다.
  3. 랭크 또는 크기: 트리의 깊이나 노드 수를 나타내어 최적화에 사용된다.

$## 구현 방식

일반적으로 배열을 사용하여 구현한다.
각 요소의 인덱스가 해당 요소를 나타내고, 배열의 값은 부모 노드의 인덱스를 저장한다.

주요 연산들의 동작 과정

  1. MakeSet(x): x를 유일한 요소로 하는 새로운 집합을 생성한다.

    • x의 부모를 자기 자신으로 설정한다.

  2. Find(x): x가 속한 집합의 대표 요소를 찾는다.

    • x에서 시작하여 부모를 따라 루트까지 올라간다.
    • 경로 압축: 탐색 과정에서 만난 모든 노드의 부모를 루트로 설정한다.

  3. Union(x, y): x와 y가 속한 집합을 합친다.

    • Find(x)와 Find(y)를 호출하여 각 집합의 대표 요소를 찾는다.
    • 랭크가 낮은 트리를 랭크가 높은 트리에 붙인다.

예시 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class DisjointSet:
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}

    def find(self, item):
        if self.parent[item] != item:
            self.parent[item] = self.find(self.parent[item])
        return self.parent[item]

    def union(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)

        if self.rank[xroot] < self.rank[yroot]:
            self.parent[xroot] = yroot
        elif self.rank[xroot] > self.rank[yroot]:
            self.parent[yroot] = xroot
        else:
            self.parent[yroot] = xroot
            self.rank[xroot] += 1

# 사용 예
vertices = ["A", "B", "C", "D", "E"]
disjoint_set = DisjointSet(vertices)

disjoint_set.union("A", "B")
disjoint_set.union("C", "D")

print(disjoint_set.find("A") == disjoint_set.find("B"))  # True
print(disjoint_set.find("A") == disjoint_set.find("C"))  # False

참고 및 출처