Union Find(유니온 파인드)

Union Find(유니온 파인드)

상호 배타적 집합을 표현할 때 쓰는 유니온 파인드라는 자료구조가 있다. 공통원소가 없는, 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조를 말하며 구현하기 위해 다음의 세 가지 연산이 필요하다.

초기화 : n개의 원소가 각각의 집합에 표함되어 있도록 초기화 한다. 합치기 연산 : 두 원소 a,b가 주어질 때 이들이 속한 두 집합을 하나로 합친다. 찾기 연산 : 어떤 원소 a가 주어질 때 이 원소가 속합 집합을 반환한다.

여기서 두 연산(합치기, 찾기)을 지원한다고 해서 유니온-파인드(union-find) 자료구조라 명명한다.

원리는 트리를 사용해서 공통의 ROOT 노드를 가지는 그룹으로 묶어나가는 것이다.

코드는 아래와 같다.

static void union(int a, int b) { a = find(a); b = find(b); if(a == b) return; parent[a] = b; } static int find(int u) { if(u == parent[u]) return u; return find(parent[u]); }

하지만 위와 같이 구성할 경우, 항상 한쪽(b)으로 이어 붙여 나가는 형식이기 때문에 만약 아래와 같이

안좋은 상황

빨간색노드를 포함하는 트리를 파란색 노드를 포함하는 트리에 병합한다고 했을 때, 높이가 붙이는 트리의 높이만큼 늘어나게 되며 Union 연산에도 O(N), Find연산에도 O(N)의 시간 복잡도를 갖게 된다. 최악의 경우 한쪽으로 길게 늘어진 기형적인 모습의 트리(..?) 형식의 모양을 갖게 되며 효율이 굉장히 나빠지게 된다. 때문에 최적화를 해주어야 한다.

첫째로 Root노드를 찾는 Find 연산을 수행할 때, 각각의 자식노드가 바로 한단계 위의 부모 노드를 가리키는 것이 아닌 Root 노드를 가리키게 한다.

둘째로 두 집합(트리)를 연결할 때는 항상 높이가 낮은 트리를 서브 트리로 삼아서 더 높은 트리에 연결해 주어야 한다.

왜냐면 위와 같은 경우에도 높이가 더 낮은 트리를 높은 트리에 연결 했더라면 트리의 높이가 더 늘어나는 것을 막을 수 있게되어 다음번에 연산을 진행 할 때, 시간복잡도를 줄일 수 있게 되기 때문이다.

최적화 코드는 아래와 같다.

static void union(int a, int b) { a = find(a); b = find(b); if(a == b) return; // 매번 트리의 높이가 더 높은 쪽으로 서브트리를 이어 붙인다 if(rank[a] > rank[b]) { int tmp = a; a = b; b = tmp; } parent[a] = b; if(rank[a] == rank[b]) ++rank[b]; // 높이가 같다면 아무 한쪽을 높임 } static int find(int u) { if(u == parent[u]) return u; return parent[u] = find(parent[u]); }

from http://sweet-smell.tistory.com/133 by ccl(A) rewrite - 2021-12-05 17:26:23