서로소 집합이란?
서로소 집합(분리 집합; Disjoints Sets)이란 공통 원소가 없는 집합들을 의미한다.
주로 트리 형태로 구현하며, 원소가 어떤 집합에 속해 있는 지 찾는 Find 연산과 두 집합을 합치는 Union 연산을 사용해 Union-Find라고도 불린다.
서로소 집합은 그 자체로도 자주 사용되지만 다른 자료 구조나 알고리즘에 적용되는 경우도 많다. (크루스칼 알고리즘, 그래프 사이클 판별, 동적 연결성 판정 등)
구현해보기 (코드)
서로소 집합은 트리 구조를 이용해 구현할 수 있는데, 같은 루트 노드를 가진 원소들은 같은 집합에 속해 있는 것이라고 보면 된다.
초기 단계
초기 단계에서는 각 원소들이 서로 다른 집합에 속해있다.
따라서 각 원소들은 자기 자신을 부모로 가진다.
각 원소들의 부모 노드를 저장하는 리스트를 하나 만들어 초기화해준다.
parents = [i for i in range(N)]
Find 연산
Find 연산은 특정 원소의 루트 노드를 찾는 연산이다.
재귀를 이용하여 간단하게 구현할 수 있다.
def find(x):
if x == parents[x]: # 루트가 자기 자신이면
return x # 리턴
return find(parents[x]) # 아니면 계속 위로 올라가기
Union 연산
Union 연산은 두 원소가 속한 집합들을 합치는 연산이다.
한 집합의 루트 노드를 다른 집합에 붙이는 방식으로 진행한다.
def union(x, y):
x = find(x)
y = find(y)
parents[x] = y
Union-Find 연산 최적화
Find 최적화: 경로 압축
기존 Find 연산은 루트 노드에 도달할 때까지 반복되어 최악의 경우 $O(N)$의 시간이 걸릴 수 있다.
따라서 매 Find 연산을 진행할 때마다 부모 노드를 루트 노드로 변경해주면 Find에 소요되는 시간을 단축할 수 있다.
다만 경로 압축을 진행할 경우 Union 연산을 Undo(되돌리기)하기 어려워지므로, 해당 연산이 필요한 경우 지양하는 것이 좋다.
def find(x):
if x != parents[x]:
parents[x] = find(parents[x]) # 부모 노드 갱신 (경로 압축)
return parents[x]
Union 최적화: Union by Rank
Union by Rank는 각 트리에 Rank를 부여해 트리의 높이를 작게 유지하는 방법이다.
Rank를 관리하는 리스트를 하나 더 만들어 Rank가 작은 트리가 큰 트리에 붙도록 구현한다.
대부분의 경우 경로 압축만 진행해도 충분히 빠르므로 필요한 경우에만 사용한다.
def union(x, y):
x = find(x)
y = find(y)
if x == y: return
if ranks[x] < ranks[y]: # x의 Rank가 y보다 크거나 같도록 SWAP
x, y = y, x
parents[y] = x
if ranks[x] == ranks[y]: # Rank가 같은 경우 임의로 붙인 후 RANK 업데이트
ranks[x] += 1
관련 문제 (BOJ)
- [1717] 집합의 표현: 서로소 집합을 그대로 사용하는 문제
- [20040] 사이클 게임: 서로소 집합으로 사이클을 판별해보자
- [4195] 친구 네트워크: 서로소 집합 + 개수 세기
- [13306] 트리: 서로소 집합에는 '분리' 연산이 없으므로, 오프라인 쿼리를 이용해 거꾸로 해결해야 한다.
