[파이썬 문법] Union find (Disjoint-set = 서로소 집합)

[그래프 알고리즘]의 일종으로 상호 배타적 집합 이라고도 불리운다.

 

서로 중복되지 않는 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 찾는 알고리즘입니다. 

 

1. Find인덱스만 참조하므로 시간복잡도는 O(1) 
2. 노드 x 가 어느 집합에 포함되어 있는지 찾는 연산
3. Union특정 집합의 원소들에 대해 상태를 바꿔줘야 하므로 시간복잡도는 O(n) 더 작은 값으로 묶는다.
4. 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산

---

parent = {}
for i in range(1,11):
    parent[i] = i

우선, 모두 연결되지 않고 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신이 가리키도록 만든다. 

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

union(1, 2)
union(2, 3)

Union(1,2), Union(3,4)를 해주어 노드를 연결한다. 그러면 노드 2의 인덱스는 1, 노드 4의 인덱스는 3이 된다.

Union(1,2), Union(2,3) 을 연결했을 때, 노드 3의 인덱스는 재귀함수를 적용해 2에서 1까지 파악할 수 있다.