유니온 파인드 알고리즘(Union Find Algorithm) |
서로소 집합(Disgoing Set) 또는 분리집합 알고리즘이라고도 불림
선택한 두 노드가 서로 같은 그래프에 속해있는지, 즉 연결되어 있는지 검사하고 연결되어 있지 않다면 두 노드를 같은 그래프에 속하도록 연결시키는 알고리즘
꼭 그래프에서만 사용하는 개념은 아닌 듯 하고 서로 공통원소가 없는 부분집합들로 나눠진 원소들에 사용할 수 있는 듯 하다.
1) Find
두 노드가 조상이 같은지 검사하는 알고리즘
즉 해당 노드가 속한 집합의 대표값을 반환한다.
재귀적으로 구성해서 부모를 타고 올라가 조상을 확인한 후 두 노드의 조상이 같은지 검사한다.
시간복잡도
배열로 구현한다면 부모 정점을 인덱스로 확인하면 되므로 O(1)
트리로 구현한다고 해도 위로 타고 올라가면 되므로 트리의 높이와 비례해서 O(H)이다.
2) Union
두 노드가 같은 조상을 가지도록 합치는 알고리즘
즉 두 집합을 합치는 연산
두 노드를 같은 그래프에 속하도록 합쳐서 연결될 수 있도록 한다.
최종적으로 모두 같은 조상 아래에 둬서 모든 노드가 연결될 수 있게 하기 위해 보통 더 작은 노드번호를 부모로 통합한다.
시간복잡도
배열의 경우 모든 원소를 순회해서 값이 y인 곳들을 모두 x로 바꿔줘야 하므로 O(N)
트리일 경우 두 트리를 합치는 작업이 필요하지만 O(N)보다는 작다.
결론적으로 배열보다 트리로 구현하는게 시간복잡도면에서 이득이다.
언제 사용하는가 |
1) MST(최소신장트리)의 크루스칼 알고리즘
2) 두 원소가 같은 집합에 속해있는지 확인하는 연산
예시 문제 : https://www.acmicpc.net/problem/1717)
3) 네트워크에 연결된 노드 수 파악
예시 문제 : https://www.acmicpc.net/problem/4195
4) 전체집합에서 구성원소들이 겹치지 않게 분할할때
분할은 분할된 두 부분집합끼리 겹치는 값이 없고 두 부분집합을 합치면 원래의 전체집합이 되는 것
예를들어 S = { 1, 2, 3, 4}가 있을 때 A = { 1, 2 } B = { 3, 4 }라면 잘 분할된것이고
C = {4} 라면 A와 C는 합쳐도 전체집합이 안되니 분할된것이 아님
함수 구현 예시 |
Parent배열에는 해당 인덱스의 부모인덱스가 들어있다.
4번의 부모가 2라면 Parent[4] = 2; 의 값이 들어있는 식이다.
처음 초기값은 자기 자신을 부모로 설정하고 시작한다.
이 모습을 상상하면 N개의 트리를 만들어 놓고 시작하는 것과 같다.
최종적으로 Parent가 { 0, 0, 0, 0 } 처럼 모두 부모가 같아진다면 하나의 트리로 완성된 것이다.
vector<int> Parent;
// 초기설정으로 본인의 부모는 본인으로
void init()
{
Parent.resize(N);
for(int i = 0; i < N; i++) {
Parent[i] = i;
}
}
// 부모를 찾는 find, 혹은 집합의 대표값
int find(int x) // getParent
{
if (Parent[x] == x) return x;
return Parent[x] = find(Parent[x]);
}
// 두 집합을 합치는 union, 서로 다른 부모(집합)일 경우 연결해주는 union 함수
void union(int x, int y) // unionParent
{
x = find(x); // 먼저 x의 부모를 찾고
y = find(y); // y의 부모를 찾아준다.
if (x < y) Parent[y] = x; // 더 작은 숫자를 부모로 병합
else if (x > y) Parent[x] = y;
// 만약 두 노드의 부모가 서로 같다면 아무 동작도 하지 않고
// 다르다면 한쪽 노드의 부모를 연결되는 다른 한쪽 노드로 설정해버림.
// 이 과정을 통해 노드 x의 부모도 x, 노드 y의 부모도 x로 부모가 같아진다.
}
특정 노드에 속한 트리의 전체 노드 수를 구하고 싶다면
/* union2(x, y): 두 원소가 속한 트리의 전체 노드의 수 구하기 */
int nodeCount[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++)
nodeCount[i] = 1;
int union2(int x, int y){
x = find(x);
y = find(y);
// 두 값의 root가 같지 않으면
if(x != y) {
// x, y 크기 비교해서 swap 해주는게 좋을듯하다.
root[y] = x; // y의 root를 x로 변경
nodeCount[x] += nodeCount[y]; // x의 node 수에 y의 node 수를 더한다.
nodeCount[y] = 1; // x에 붙은 y의 node 수는 1로 초기화
}
return nodeCount[x]; // 가장 root의 node 수 반환
}
※ 참고 문헌
https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html#google_vignette