참고
서로소 집합과 연산(Union & Find)
NOTE
서로소 집합 → 공통 원소가 없는 두 집합을 의미 (교집합이 없음)
•
•
NOTE
•
서로소 집합 → 공통 원소가 없는 두 집합을 의미 (교집합이 없음)
•
서로소 집합 자료구조는 union, find 2가지 연산으로 이루어짐
◦
union : 2개의 원소가 각각 포함되어 있는 집합을 하나로 합침
◦
find : 특정한 원소가 속한 집합이 어떤 집합인지 찾음
•
서로소 집합 표현방법
◦
연결 리스트
◦
트리
•
시간복잡도
서로소 집합의 구현 (생성 및 초기화)
NOTE
•
0~4 까지의 원소를 각각 가진 5개의 서로소 집합이 있다고 가정
•
처음 서로소 집합을 만들 때는, 자기 자신을 집합의 부모라고 간주한다.
◦
0 → 부모가 0인 집합
◦
1 → 부모가 1인 집합 ..
int[] set = new int[5];
for (int i = 0; i < 5; i++) {
set[i] = i;
}
Java
복사
•
이제 union & find 연산을 위해 집합을 두 그룹으로 나눔
set[0] = 1;
set[2] = 3;
set[3] = 4;
Java
복사
서로소 집합의 구현 - Find 함수
NOTE
•
자신이 속한 집합을 찾는 find 연산을 코드로 구현
•
자신이 속한 집합의 대표로 집합을 구분하고, 대표를 보통 부모라고 부름
static int find(int[] parent, int i){
if(parent[i] == i){
return i;
}
return find(parent, parent[i]);
}
Java
복사
서로소 집합의 구현 - Union 함수
NOTE
•
이제 A와 B의 집합을 합친다
•
두 집합을 합칠 때, 어느 쪽으로 합칠지는 자유이나 지금은 원소 값이 더 작은 쪽으로 합친다
◦
따라서 A와 B를 합치는 경우 모두 A쪽으로 넣음
•
집합을 구분하는 요소가 집합의 ‘부모’원소 이므로 B집합의 부모를 A 집합의 부모로 교체한다
static void union(int[] parent, int a, int b){
int a_parent = find(parent, a);
int b_parent = find(parent, b);
if(a_parent < b_parent)
parent[b_parent] = a_parent;
else
parent[a_parent] = b_parent;
}
...
union(set, 1, 4);
System.out.println(Arrays.toString(set));
// [1, 1, 3, 4, 1] -> 4가 b의 부모인데 1로 변경됨
Java
복사
연산의 효율을 높이는 법
NOTE
•
Rank를 이용한 Union 기법
◦
각 노드는 자신을 루트로 하는 subTree의 높이를 rank로 지정
◦
두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙임
•
Path compression
◦
Find-set을 행하는 과정에서 만나는 모든 노드들이 root를 직접 가리키도록 함
rank 기법
NOTE
•
두 집합을 합치는 과정에서 아무런 기준없이 합치게된다면, 트리의 깊이가 깊어지는 문제가
발생하게 된다.
원소의 개수가 적은 집합이 흡수되는 경우 높이 변화 x
원소의 개수가 큰 집합이 흡수되면 높이변화가 생김
•
이렇게 깊이가 점점 깊어진다면 Find 연산이 재귀의 형태로 이루어져 있으므로 최악의경우
O(n)의 시간복잡도를 가지게 된다.
•
Rank를 사용하게 되는 경우, 시간 복잡도를 O(logN)까지 줄일 수 있다.
Path Union 기법
NOTE
Find 하는 과정에서 각 부모를 모두 최종 부모로 갱신 시켜주는 방식
경로 압축을 통한 최종 트리 구조