[Algorithm/Python] Disjoint Set(서로소 집합)이란? Union-Find 알고리즘 정리

서로소 집합(Disjoint Set)이란?

서로 중복되지 않는 부분(서로소) 집합. 

서로 다른 원소들이 같은 집합에 속해 있는지 여부를 확인하는데 사용.

 

이 서로소 집합을 나타내기 위해 사용되는 알고리즘으로 Union-Find 알고리즘이 있다.

 

Union-Find 알고리즘

각 그룹을 트리의 형태로 표현. 각 트리는 항상 최상위 노드인 루트 노드를 가진다.

이 루트 노드를 가지고 그룹을 판별한다.

(root 노드는 자신을 부모 노드로 설정)

 

1. union 연산을 확인하며, 서로 연결된 두 노드 A, B를 확인한다.
   1. A와 B의 루트 노드를 각각 찾는다.
   2. A의 루트 노드를 B의 부모 노드로 설정한다.
2. 모든 union 연산 처리할 때까지 이전 과정을 반복한다.

 

Find

어떤 노드가 주어졌을 때 이 노드가 속한 집합의 root 노드를 찾는 작업

특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

def find(x):
	if x == parent[x]:
		return x
	
	return find(parent[x])

Union

두 집합 트리를 병합하여 하나의 트리로 만드는 작업

2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

def union(a, b):
	a = find(a)
	b = find(b)

	if (a != b):
		parent[b] = a

 

시간 복잡도의 문제

이미지 출처: 이것이 코딩테스트다 with python

 

위 그림처럼 V개 노드의 선형 그래프인 경우, 노드 5의 루트 노드를 찾기 위해선 최대 O(V) 시간이 소요될 수 있다.

노드 개수가 V개이고 find 혹은 union 연산의 개수가 M개일 때, 전체 시간 복잡도는 O(VM)이 되어 비효율적이다.

 

이를 해결하는 방법에는 트리의 높이를 최소화하는 방법이 있다.

크게 경로 압축(Path Compression)과 유니온 바이 랭크(Union by rank) 방법이 있다.

 

경로 압축(Path Compression)

find 함수를 재귀적으로 호출한 뒤에 부모테이블 값을 갱신하는 기법.

 

경로 압축 기법의 find 함수

def find(parent, x):
	if parent[x] != x:
    	parent[x] = find(parent, parent[x])
    return parent[x]

경로 압축 (이미지 출처: 이것이 코딩테스트다 with python)

유니온 바이 랭크(Union by rank)

항상 작은 트리를 큰 트리 루트에 붙이는 방법.

작은 트리는 상대적으로 높이가 낮거나 작은 트리를 의미한다.

def unionbyrank(parent, rank, a, b):
    a = find(parent, a)
    b = find(parent, b)

    if a == b:
        return
    if rank[a] > rank[b]:
        parent[b] = a
    elif rank[a] < rank[b]:
        parent[a] = b
    else:
        rank[b] += 1
        parent[a] = b