♣️ 유니온 파인드(Union-Find = Disjoint-set)?
크루스칼 알고리즘에서 두 정점이 같은 그룹인지 확인하고, 다르면 같은 그룹으로 합칠 때 이 알고리즘을 활용한다.
일반 구현으로는 $O(V+E)$의 시간이 걸리지만, 유니온 파인드를 사용하면 상수시간에 가깝게 해결할 수 있다.
Union 연산 : 두 그룹을 합치는 연산
Find 연산 : 원소가 속해있는 그룹을 알아내는 연산
♣️ Find(int x) 구현방법
트리 구조를 각 원소에 대해 부모 정점의 번호를 담을 배열을 만들고 값을 적절히 사용한다.
각 원소를 정점으로 생각하고 그룹은 트리로 표현한다. 그리고 모든 원소에 대해 부모 정점이 없다는 뜻으로 -1을 채워둔다.
- 재귀를 활용해, 자신의 부모 노드로 타고 올라간다.
- 현재 노드의 값이 음수(-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 연산이 발생하면, 한 트리의 루트가 다른 트리의 자식으로 들어가서 두 개의 트리가 합쳐진다.
- u가 속한 트리와 v가 속한 트리를 찾는다.
- 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이면 루트노드를 의미했지만,
- 트리의 높이가 증가함에 따라 -2, -3, -4로 값을 감소시킨다.
- 두 트리의 높이가 같다면, 한 쪽 트리의 높이를 1 증가시킨다.
- 높이가 같은 트리를 합치게 되면, 트리의 높이가 1 증가하기 때문이다.
- 높이가 낮은 트리의 루트를 높이가 더 높은 트리의 자식으로 만든다.
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
'자료 구조 & 알고리즘(Data Structure & Algorithm) > 알고리즘(Algorithm)' 카테고리의 다른 글
[알고리즘] 위상정렬 복습 겸 정리 (1) | 2024.12.20 |
---|---|
[알고리즘] 다익스트라 역방향 그래프 (0) | 2024.12.02 |
[알고리즘] 최소신장트리(Minimum Spanning Tree) 복습 겸 정리 (2) | 2024.11.27 |
[알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) 기초 (0) | 2024.11.21 |