[알고리즘🧩] Union-Find (Disjoint-sets)

목차

💬 서로소 집합 (Disjoint-sets)

 

---

💬 서로소 집합(Disjoint-sets)

💡 서로소 집합(Disjoint-sets)

서로소 또는 상호배타 집합들로, 교집합이 없는 집합들을 의미한다.
집합에 속한 하나의 특정 멤버를 통해 집합들을 구분하는데, 이를 대표자(representative)라고 한다.

 

• 상호배타 집합 표현 방법
  • 연결 리스트
  • 트리
• 상호배타 집합 연산
  • Make - Set(x)
    유일한 멤버 x를 포함하는 새로운 집합을 연산하는 연산
    
    
  • Find - Set(x)        return {representative}
    x를 포함하는 집합을 찾는 연산
    
    
  • Union(x, y)
    x와 y를 포함하는 두 집합을 통합하는 연산

📌 상호배타 집합의 예

 

 

✅ 상호 배타 집합 표현 - 연결리스트

같은 집합의 원소들을 하나의 연결리스트로 관리하며, 연결리스트의 맨 앞 원소가 대표 원소(representative)가 된다.

• 각 원소는 집합의 대표원소(representative)를 가리키는 링크를 가진다.

•  Find-Set(e)                 return a
• Find-Set(f)                   return b
• Union(a, b)

 

 

✅ 상호 배타 집합 표현 - 트리

하나의 집합(a disjoint set)을 하나의 트리로 표현하는 것이다.

• 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자(representative)가 된다.

 

• Make-Set(a) ~ Make-Set(f)

• Union(c, d), Union(e, f)

• Union(d, f)

Find-Set(d) = Find-Set(e) = return c

📌 상호 배타 집합 연산(트리)의 문제점

트리의 표현을 사용하면 Union(x, y) 연산을 수행할 때 루트 하나의 정보만 변경하면 된다는 장점을 가진다. 그러나 연산의 순서에 따라 잘못하면 트리가 한쪽으로 기울어지는 문제가 발생할 수 있다.

▷ 트리의 높이가 h가 되면 Union()연산과 Find-Set() 연산 모두 시간복잡도가 O(h)가 되어버리며, 배열로 구현하는 것보다 효율이 더 나빠진다.


▶ 해결(최적화) 방안

- Rank를 활용한 Union (랭크에 의한 합치기 최적화)
각 노드는 자신을 루트로 하는 subtree의 높이를 랭크(rank)라는 이름으로 저장한다. 그리고 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다.

p[x]: 노드 x의 부모 저장
rank[x]: 루트 노드가 x인 트리의 랭크 값 저장


Make_Set(x):
	p[x] = x
    rank[x] = 0
    

Find_Set(x):
	# x가 루트가 아닌 경우
	if x != p[x]:
    	p[x] = Find_Set(p[x])
    return p[x]
    

Union(x, y):
	Link(Find_Set(x), Find_Set(y))


Link(x, y):
	# rank는 트리의 높이
	if rank[x] > rank[y]:
    	p[y] = x
    else
    	p[x] = y
        if rank[x] == rank[y]:
        	rank[y] += 1

 

→ Find_Set() 연산은 특정 노드에서 루트까지의 경로를 찾아가면서 노드의 부모 정보를 갱신한다.


- Path Compression (경로 압축)
Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 변경해준다.