서로소 집합 자료구조 중 하나로 무향 그래프의 연결된 요소들을 추적할 수 있다.(by 위키백과)
위키에 있는 의사코드를 보면 상당히 간단하게 구현이 가능하다.
function MakeSet(x) x.parent := x
function Find(x) if x.parent == x return x else return Find(x.parent)
function Union(x, y) xRoot := Find(x) yRoot := Find(y) xRoot.parent := yRoot
위 모양은 단순한 형태로 구현한 것이다.
위 코드에서 문제점이 있는데 사향 이진 트리와 같은 모양으로 구성되면 매우 비효율 적이다.
그렇기 때문에 Find(x)함수에서 약간의 처리를 해주면 된다.
function Find(x) if x.parent != x x.parent := Find(x.parent) return x.parent
흔히 경로 압축이라고 부르는 방법으로 파인트 연산을 수행 할 때마다 트리의 구조를 평평하게 만들는 방법이다.
위와 같은 모양을 아래와 같이 바꿔준다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | /*Union Find 구현*/ #include <iostream> #define SIZE 10 using namespace std; int parent[SIZE + 1]; void set_() { for (int i = 1; i <= SIZE; i++) parent[i] = i; } int find(int target) { if (target == parent[target]) return target; else return parent[target] = find(parent[target]); } void Union(int a, int b) { a = find(a); b = find(b); if (a != b) parent[b] = a; } void PRINT_() { for (int i = 1; i <= SIZE; i++) { cout << i << ' '; } cout << '\n'; for (int i = 1; i <= SIZE; i++) { cout << parent[i] << ' '; } cout << '\n' << '\n'; } int main() { ios::sync_with_stdio(0), cin.tie(0); set_(); cout << "초기값" << '\n'; PRINT_(); cout << "(1,7 Union)" << '\n'; Union(1, 7); PRINT_(); cout << "(7,2 Union)" << '\n'; Union(7, 2); PRINT_(); cout << "(9,2 Union)" << '\n'; Union(9, 2); PRINT_(); for (int i = 1; i <= SIZE; i++)find(i); cout << "최종적으로 경로 압축" << '\n'; PRINT_(); return 0; } | cs |
'알고리즘' 카테고리의 다른 글
CCW (0) | 2020.04.04 |
---|---|
피보나치 수 (0) | 2020.04.04 |
Bubble Sort (거품정렬) (0) | 2018.10.27 |
[알고리즘] Select Sort (선택정렬) (0) | 2018.10.27 |
[알고리즘] MergeSort (0) | 2018.10.26 |
댓글