[알고리즘] 유니온 파인드 알고리즘(Union-Find) 복습 겸 정리

♣️ 유니온 파인드(Union-Find = Disjoint-set)?

크루스칼 알고리즘에서 두 정점이 같은 그룹인지 확인하고, 다르면 같은 그룹으로 합칠 때 이 알고리즘을 활용한다.

일반 구현으로는 $O(V+E)$의 시간이 걸리지만, 유니온 파인드를 사용하면 상수시간에 가깝게 해결할 수 있다.

Union 연산 : 두 그룹을 합치는 연산

Find 연산 : 원소가 속해있는 그룹을 알아내는 연산

♣️ Find(int x) 구현방법

트리 구조를 각 원소에 대해 부모 정점의 번호를 담을 배열을 만들고 값을 적절히 사용한다.

각 원소를 정점으로 생각하고 그룹은 트리로 표현한다. 그리고 모든 원소에 대해 부모 정점이 없다는 뜻으로 -1을 채워둔다.

1. 재귀를 활용해, 자신의 부모 노드로 타고 올라간다.
2. 현재 노드의 값이 음수(-1)이면, 루트노드를 의미하므로 return x 한다.

public static int Find(int x){
	if(tree[x]<0) return x;
	return Find(tree[x]);
}

♣️ Union(int u, int v) 구현방법

Union 연산이 발생하면, 한 트리의 루트가 다른 트리의 자식으로 들어가서 두 개의 트리가 합쳐진다.

1. u가 속한 트리와 v가 속한 트리를 찾는다.
2. v가 속한 트리의 루트를 u가 속한 트리의 루트 자식으로 만든다.

public static void Union(int u, int v){
	u = Find(u); // u의 루트노드
	v = Find(v); // v의 루트노드
	if(u!=v) trre[v] = u; // 루트노드가 다르면 합친다.
}

♣️ 유니온 파인드 최적화

union은 한 트리의 루트를 다른 트리의 루트 자식으로 만들기에 실행시간이 $O(1)$에 동작한다.

find의 실행시간이 유니온 파인드 전체 시간복잡도에서 중요하게 작용한다.

find는 최악의 경우 $O(N)$의 수행시간이 걸려 비효율적인 구조가 된다.

따라서, 최적화를 추가로 적용해야 효율적인 자료구조로 사용할 수 있다.

최적화 1 : Union By Rank → $O(logN)$

union 연산을 할 때, 트리의 높이를 고려해서 합치는 방법이다.

트리의 높이를 최대한 낮게 유지하는게 실행시간이 적게 걸리게 된다.

1. 부모의 정점을 저장하는 배열에서 트리의 높이도 같이 관리한다.
   • 부모의 정점이 -1이면 루트노드를 의미했지만,
   • 트리의 높이가 증가함에 따라 -2, -3, -4로 값을 감소시킨다.
2. 두 트리의 높이가 같다면, 한 쪽 트리의 높이를 1 증가시킨다.
   • 높이가 같은 트리를 합치게 되면, 트리의 높이가 1 증가하기 때문이다.
3. 높이가 낮은 트리의 루트를 높이가 더 높은 트리의 자식으로 만든다.

public static void Union(int u, int v){
	u = Find(u); // u의 루트노드
	v = Find(v); // v의 루트노드
	if(tree[v] < tree[u]) swap(u,v); // u의 높이가 항상 더 높게 고정한다.
	if(tree[u] == tree[v]) tree[u]--; // 높이가 같다면 높이를 증가시킨다.
	tree[v] = u; // v를 u의 자식으로 만든다. 
}

---

최적화 2 : 경로 압축 → Amorized $O(logN)$

find 연산을 할 때, 경로를 압축하여 루트노드를 효율적으로 찾는 방법이다.

루트노드를 찾으면서 부모노드를 타고 올라갈 때 만난 노드의 부모를 루트노드로 변경한다.

이를 통해, 트리의 높이를 간단하게 낮출 수 있다.

경로 압축 최적화는 연산을 1번하면, 최대 $O(N)$이 걸릴 수 있지만, 그 후엔 $O(1)$이 걸려 전체 시간을 합쳐보면 $O(logN)$이다.

public static int Find(int x){
	if(tree[x]<0) return x;
	// 기존에 Find(tree[x])만 반환하는걸, tree[x]에 대입할 수 있게 변경한다.
	return tree[x] = Find(tree[x]);
}

최적화 3 : Union By Rank + 경로 압축

2가지 최적화 방법을 모두 사용한다면, 실행 시간은 Amorized $O(α(N))$으로 사실상 상수시간이다.

알고리즘 시험에서는 최적화 2개 중 하나만 적용해도 시간초과 날 걱정하지 않아도 된다!

♣️ 유니온 파인드 알고리즘 문제 목록

[백준] 1717번 : 집합의 표현 - 자바(Java)

[백준] 20040번 : 사이클 게임 - 자바(Java)

♣️ 참고자료

BaaaaaaaarkingDog : [실전 알고리즘] 부록 D - Union-Find