[자료구조] Union Find

Disjoint Set

DisJoint Set이란?

서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

 

- 즉, 공통 원소가 없는 "상호 배타적"인 부분집합들로 나눠진 원소들에 대한 자료구조

- Disjoint Set=서로소 집합 자료구조

 

Union-Find

Union-Find란?

Disjoint Set을 표현할 때 사용하는 알고리즘

 

-집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그 중 가장 효율적인 트리 구조를 이용하여 구현

-아래의 세가지 연산을 이용하여 Disjoint Set을 표현

 

Union-Find의 연산

- make-set(x)

• 초기화
• x를 유일한 원소로 하는 새로운 집합을 만든다.

- union(x,y)

• x가 속한 집합과 y가 속한 집합을 합친다. 즉, x와 y가 속한 두 집합을 합치는 연산

-find(x)

• x가 속한 집합의 루트 노드 값을 반환한다. 즉,x가 어떤 집합에 속해 있는지 찾는 연산

※ 트리로 구현했을 때

 - 같은 집합=하나의 트리, 즉 집합 번호=루트 노드

 - 시간복잡도

• union(x,y) : O(n)보다 작으므로 find연산이 전체 수행 시간을 지배
• find(x) : 트리의 높이와 시간 복잡도가 동일 ( 최악 : O(N) )

구현

parent[i]를 i 노드의 부모 노드라고 정의하고 초기화 해준다.

parent[i] = i 인경우, 루트 노드임을 의미한다.

//초기화
int parent[MAX_SIZE];

for (int i=0; i<MAX_SIZE; i++)
  parent[i] = i;

//fin함수 : 부모노드 찾기
int find(int x){
  if (x==parent[x]){
    return x;
  }
  else {
    return find(parent[x]);
  }
}

//union함수 : x의 집합과 y의 집합 합치기
void union(int x,int y){
  x = find(x);
  y = find(y);
  if (x!=y)
    parent[y] = x;
}

 

개선해야 될 점

- find함수에서 재귀적으로 루트를 찾아 반환해주면 그림과 같이 깊이가 깊어진 경우(최악의 경우) O(N)의 시간복잡도가 걸린다. 그래서 아래와 같이 개선해 준다.

int find(int x){
  if (x==parent[x]){
    return x;
  }
  else{
    int y = find(parent[x]);
    parent[x] = y;
    return y;
  }
}

- union 함수에서 높이가 더 높은 트리가 낮은 트리 밑으로 들어가게 되면 트리가 점점 깊어질 위험이 있다. 

따라서 트리의 높이가 낮은 트리가 높은 트리 밑으로 들어가야 하는데 이를 위해서 트리의 높이를 기록해둬야 한다.

-> 추가적인 배열이 필요

 

결론 ) parent배열과 트리의 높이를 기록해주는 배열이 필요하므로 메모리를 두배로 사용하기 때문에

weight Union find 방법이 고안되었다.

 

weighted Union Find

parent 배열이 음수일 경우, 부모노드가 되어 음수의 절대값은 size(자기 자신+자식노드)가 되고, 양수일 경우에는 부모노드를 가르키게 된다.

예를 들어 parent[2]=-3인 경우 2번 노드 밑에 두 개의 자식 노드가 있어 총 3개의 노드가 존재한다는 의미이고,

parent[3]=5일 경우에는 3번 노드의 부모가 5번 노드라는 의미이다.

int parent[MAX_SIZE];

for (int i=0; i<MAX_SIZE; i++)
  parent[i] = -1;

int find(int x){
  if (parent[x] < 0){
    return x;
  }
  else{
    int y = find(parent[x]);
    parent[x] = y;
    return y;
  }
}

void union(int x, int y){
  x = find(x);
  y = find(y);
  
  if (x == y)
    return;
  
  // parent[x], parent[y] 값은 음수이므로 값이 작은 경우가 더 높이가 큰 노드이다.
  if (parent[x] < parent[y]){
    parent[x] += parent[y];
    parent[y] = x;
  }
  else {
    parent[y] += parent[x];
    parent[x] = y;
  }
}

 

관련 문제 

백준 1717 집합의 표현 : www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

참고

gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

ssungkang.tistory.com/m/entry/Algorithm-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find

[Algorithm] 유니온 파인드(Union - Find)