Union-Find 알고리즘

Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘

간단하게 노드들 중에 연결된 노드를 찾거나, 노드들을 서로 연결할 때 사용한다

Disjoint Set 이란

• 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
• 공통 원소가 없는 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조
• = 서로소 집합 자료구조

1. 초기화

• n 개의 원소가 개별 집합으로 이뤄지도록 초기화

2. Union

• 두 개별 집합을 하나의 집합으로 합침, 두 트리를 하나의 트리로 만든다.

func union(_ x: String, _ y: String) {
	let parentX = find(x)
    	let parentY = find(y)
    
   	 if parentX != parentY {
    		parent[parentY] = parentX
        }
}

union(a,b)의 의미 : find(a)(= a의 부모노드)와 find(b)(= b의 부모노드) 를 비교하여 만약 다르다면 b의 부모노드를 a의 부모노드와 같게 한다.

3. Find

• 여러 노드가 존재할 때, 두 개의 노드를 선택해서 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 각 그룹의 최상단 원소(루트 노드) 확인

func find(_ x: String) -> String {
	if parent[x] == x {
    		return x
        } else {
        	let topParent = find(parent[x]!)
            	parent[x] = topParent
            	return parent[x]!

find(a)의 의미 : 자신이 가리키고 있는 부모를 재귀적으로 찾아 실질적인 부모노드를 가져온 뒤 자신의 부모로 삼음