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

유니온 파인드 알고리즘이란?

그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set 이라고도 합니다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘입니다. 그러기 위해 두 가지 연산이 존재합니다.

1. Find

   노드 x 가 어느 집합에 포함되어 있는지 찾는 연산

2. Union

   노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산

 

유니온 파인드 구현

구현은 간단한 트리를 통해서 이루어집니다.

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

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

int parent[MAX_SIZE];

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

 

find 함수 구현

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

x == parent[x] 라면 부모노드가 자기자신, 즉 본인이 루트노드라는 의미입니다. 따라서 이 자체를 그대로 return 해줍니다. 그렇지 않다면 재귀적으로 루트를 찾아 반환해줍니다.

다음과 같이 find 를 구현한 경우 문제점이 발생합니다.

 

위 그림과 같이 한 쪽으로만 tree 가 치우져진 경우, find 함수가 루트노드를 찾는데 O(N) 의 시간복잡도가 걸려 tree 로 구현하는 이점이 사라집니다. 이를 해결하기 위해서 다음과 같이 개선할 수 있습니다.

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

루트노드인 y 를 찾았으면 x 의 부모를 바로 루트노드로 바꿔주어 아래와 같이 바꿔줍니다. 결과적으로 아래 그림과 같이 바꿔 find 의 효율을 올려줄 수 있습니다.

 

 

union 함수 구현

union 함수는 매개변수로 두 개의 값을 받습니다. 두 노드가 각 포함되어있는 집합을 합쳐줘야 하는데 편의상 union(x,y) 에 대해 y 의 집합을 x 의 집합에 합치도록 하겠습니다. 즉, y 의 parent 가 x 가 되는 것이죠.

void union(int x,int y){
  x = find(x);
  y = find(y);
  if (x!=y)
    parent[y] = x;
}

find 를 통해 각각의 root 를 찾아준 후, 두 집합의 root 가 다른 경우 y 의 부모노드를 x 로 바꿔주도록 합니다.

 

하지만 이 경우도 문제점이 발생합니다.

높이가 더 높은 트리가 높이가 낮은 트리 밑으로 들어가게 되면 트리가 점점 깊어질 위험이 있습니다. 따라서 트리의 높이가 낮은 트리가 높은 트리 밑으로 들어가야 하는데 이를 위해서는 트리의 높이를 기록해두어야 합니다.

트리의 높이를 기억하는 rank 라는 배열을 선언하고 초기화 해줍니다.

int rank[MAX_SIZE];

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

 

이제 union 할 시 크기를 비교해주고 합쳐줄 경우에는 크기를 갱신해주어야합니다.

void union(int x, int y){
  x = find(x);
  y = find(y);
  
  if (x == y)
    return;
  
  if (rank[x] > rank[y]){
    parent[y] = x;
    rank[x] += rank[y];
  }
  else {
    parent[x] = y;
    rank[y] += rank[x];
  }
}

 

Weighted Union Find

하지만 이럴 경우, parent 배열도, size 배열도 존재하여 메모리를 두 배로 사용하게 됩니다. 그래서 이를 개선하고자 Weighted Union Find 방법이 고안되었습니다. 이는 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;
  }
}