Disjointed set(union find)알고리즘을 통해 여러 개의 원소들 중, 두 원소가 서로 같은 집합에 속해있는지 아닌지 판별할 수 있습니다.
두 원소가 같은 집합에 속해있는지 판별하기 위해서는 크게 두가지 기능이 필요합니다.
- 두 원소 a, b가 속한 집합을 합치기 (union)
- 두 원소 a, b가 주어졌을 때 같은 집합인지 판별하기 (find)
Union(합치기) 연산
parent 배열에는 원소 i가 속해있는 집합을 뜻합니다.
원소 1, 2 를 합치면 parent 배열은 다음과 같이 됩니다.
두 원소의 parent값을 비교하여 두 값이 서로 다른 경우,
한 쪽의 parent값을 다른 한 쪽의 parent값으로 합칩니다.
다음은 이를 구현한 코드 입니다.
void Union(int a, int b){
int parentA = getParent(a);
int parentB = getParent(b);
if(parentA != parentB) parent[b] = parentA;
// parent[a] = parentB 로 해도 상관 없음
return;
}위의 코드에서 각 원소가 속한 집합을 찾는 getParent는 다음과 같습니다.
int getParent(int a){
//parent[a]가 자신과 같을 경우 a를 반환
//다를 경우 재귀 함수를 통해 parent[a] 값의 parent를 찾는다.
if(a == parent[a]) return a;
return getParent(parent[a]);
}Union 연산의 시간복잡도
최악의 경우 : 다음과 같이 parent 배열이 주어졌을 때 union(6, 7) 연산을 수행하면 getParent(6) 수행 시, O(n) 만큼의 시간이 걸리게 됩니다.
위와 같이 O(n)의 시간복잡도는 원소의 갯수와 연산 횟수가 늘어날수록 더 오래 걸리게 됩니다.
union연산을 최적화 하기 위한 경로 압축 알고리즘을 다음 장에서 다루겠습니다.
Find(찾기) 연산
find 연산은 앞서 만들어 놓은 getParent 함수를 이용하여 다음과 같이 구현합니다.
bool find(int a, int b){
int parentA = getParent(a);
int parentB = getParent(b);
if(parentA == parentB) return true;
return false;
}두 원소 a, b의 parent 값으 비교하여 값이 같으면 같은 집합에 속해있으므로 true를 반환합니다. 두 값이 다를 경우는 false를 반환합니다.
find 연산의 시간복잡도
find 또한 union에서 발생한 시간복잡도와 같은 맥락으로 getParent연산을 수행할 때 최악의 경우 O(n) 만큼의 시간이 걸리게 됩니다.
전체 소스코드
#include <stdio.h>
int parent[8];
int getParent(int a){
if(a == parent[a]) return a;
return getParent(parent[a]);
}
void Union(int a, int b){
int parentA = getParent(a);
int parentB = getParent(b);
if(parentA != parentB) parent[b] = parentA;
return;
}
bool find(int a, int b){
int parentA = getParent(a);
int parentB = getParent(b);
if(parentA == parentB) return true;
return false;
}
int main(){
for(int i = 1 ; i<=7 ; i++) parent[i] = i;
Union(1, 2);
Union(2, 3);
Union(7, 1);
printf("%d %d : %s\n", 1, 3, find(1, 3)?"union" : "not union");
printf("%d %d : %s\n", 1, 7, find(1, 7)?"union" : "not union");
printf("%d %d : %s\n", 1, 7, find(4, 7)?"union" : "not union");
return 0;
}
참고문헌
