유니온 파인드(Union-find)

목차

개요 초기화 간단한 방법 최적화 단계 1 최적화 단계 2 - 유니온 파인드 트리 유니온 파인트 트리 - 코드 문제

개요

집합을 관리하는 자료구조로서, disjoint set이라고 부르기도 합니다. 이 자료구조를 활용하면 아래의 두 가지 연산을 수용할 수 있습니다. 요소 에이와 요소 비가 같은 집합에 속하는지 확인. 요소 에이가 속한 집합과 요소 비가 속한 집합을 병합. 이런 식의 두 연산을 효율적으로 하기 위한 자료구조가 유니온 파인드, disjoint set 입니다.

초기화

초기 상태는 각각의 요소가 따로 따로 집합에 속하는 상태입니다. 이 상태를 만들어 주는 간단한 방법으로 아이번째 요소는 아이번째 집합에 속한다 라고 지정하는 방법이 있습니다.

간단한 방법

same_set()함수의 시간복잡도는 O(1) merge() 함수의 시간복잡도는 O(N)으로 효율은 좋지 않습니다. 우선 초기화 파트에서 설정한 그룹 배열을 가지고 있다면, same_set 연산은 굉장히 간다내 집니다. 요소 에이와 요소 비가 같은 집합에 속하는 지에 대한 판별은 그룹에이와 그룹비로 가능하기 때문입니다. 병합의 경우엔, 요소 비가 속한 집합의 요소들을 전부 요소 에이가 속한 집합으로 옮기면 됩니다. 따라서 아래와 같이 코딩할 수 있습니다.  간단하지만 그룹아이와 그룹브이2로 하면 안되는 점을 주의해야 합니다. 그럴 경우, 반복문 중간에 그룹 브이2가 그룹브이1으로 바뀌기 때무넹 아이는 브이2 인 요소들은 제대로 병합이 되지 않습니다.  이 간단한 방법을 활용하면 모든 요소가 하나의 집합이 될 때까지 총 시간 복잡도는 O(N^2)입니다. 이는 굉장히 비효율적인 시간 복잡도 이기 때문에 잘 쓰이지 않습니다.

최적화 단계 1

각 집합에 어떤 요소들이 있는 지를 저장하면 머지 에서 모든 요소들을 순회할 필요가 없다 라는 아이디어 입니다. 멤버아이는 아이집합에 속한 요소들의 번호들을 저장한 동적 배열 입니다. 그리고 멤버 아이 제이는 아이 집합에 속한 요소 중 제이 번째 요소입니다.

최적화 단계 2 유니온

멤버와 그룹을 없애고, 각 집합을 배열이 아닌 트리의 형태로 관리하면 더 빠른 자료구조를 만들 수 있습니다. 패런트 즉 트리에서의 부모를 저장합니다. 개요에 있는 상황을 트리로 표현하면 다음과 같습니다. 이 방법에서는 집합의 번호를 루트 요소의 번호로 대신합니다. 따라서 집합의 번호를 찾고 싶을 땐, 루트 노드를 찾아 올라가면 됩니다.   이 함수가 얼마나 큰지 감각적으로 알기 힘들다면, 오1보다 느리고 오1보다 느리고 오 로그엔보다 빠르다. 모든 요소가 하나의 집합에 속할 때 까지의 총 시간복잡도는 오엔보다 느리고 오엔로그엔보다 빠릅니다. 유니온 파인드 트리 - 코드

#include<stdio.h> #include<algorithm> #include<vector> #include<iostream> using namespace::std; const int N = 1000000; struct union_find_tree { vector<int> parent; vector<int> height; vector<int> group_size; void init(int uf_n) { parent.clear(), height.clear(); group_size.clear(); for (int i = 0; i<uf_n; i++) { parent.push_back(i); height.push_back(0); group_size.push_back(1); } } int get_root(int now) { if (parent[now] == now) return now; return parent[now] = get_root(parent[now]); } bool same_set(int v1, int v2) { return get_root(v1) == get_root(v2); } void merge(int v1, int v2) { v1 = get_root(v1), v2 = get_root(v2); if (v1 == v2) return; if (height[v1] < height[v2]) swap(v1, v2); parent[v2] = v1; group_size[v1] += group_size[v2]; if (height[v1] == height[v2]) height[v1]++; } }uf; int main() { int n, m; cin >> n >> m; //scanf("%d %d", &n, &m); uf.init(n + 1); while (m--) { int ty, v1, v2; cin >> ty >> v1 >> v2; //scanf("%d %d %d", &ty, &v1, &v2); if (ty == 0) uf.merge(v1, v2); else cout << (uf.same_set(v1, v2) ? "YES" : "NO") << endl ; //else printf("%s\n", uf.same_set(v1, v2) ? "YES" : "NO"); } cout << "end" << endl; return 0; }

- 구조체를 사용해서 트리의 구조를 나타냄으로써 2가지 기능을 사용할 수 있습니다. - 그룹과 그룹간의 합하는 기능 - 그리고 같은 그룹에 속해 있는지 확인하는 기능입니다. - 그래서 필요한 변수는 벡터 인트 부모. 벡터 인트 높이. 벡터 인트 그룹 사이즈 입니다. - 그리고 초기화를 하는데. 처음 패런트에는 1,2,3,4,5, .. 각각 독립적으로 들어있음을 의미합니다. - 그리고 높이는 모두 시작은 0입니다. 그리고 다른 한개가 들어오면 1이 됩니다. - 그리고 그룹 사이즈도 자기 자신만 가지고 있으므로 1로 선언합니다. - 부모 루트를 알기 위해서 겟 루트 함수를 선업합니다. - 자기 자신이라면 단순하게 자기자신을 출력하면 됩니다.   자기자신이 아니라면 패런트[나우]. 재귀를 통해서 부모 노드를 찾아갑니다. - 같은지 확인하는 것은 부모노트를 확인하면 됩니다. 가장 높은 것이 같으면 오케이. - 그리고 통합하는 함수는 2개의 변수를 입력 받습니다.    브이1, 브이2가 있습니다. 각각 부모노드를 다시 찾은 다음에 같으면 통합이 이미 되어 있으므로 리턴    만약 헤이트가 브이2가 더크다면. 아 트리가 큰 것이 앞으로 와야 합니다.    그리고 작은 브이2의 부모는 브이1을 넣습니다.     그리고 그룹사이즈를 흡수합니다.    만약 헤이트가 같으면, 큰 것의 헤이트를 하나 올립니다. - 이렇게 정리하니까 어렵지 않은 것 같습니다. - 내일 아침에 다시 스스로 짜보도록 하겠습니다.

http://weeklyps.com/entry/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Unionfind