Union-Find (합집합 찾기)

Union-Find는 그래프 알고리즘 중 하나입니다. 합집합 찾기 또는 서로소 집합(Disjoint-Set) 알고리즘이라고 불립니다.

같은 그래프 내에 확인하고 싶은 노드들이 있는지 확인할 수 있는 알고리즘입니다. 

 

Union-Find를 구현하기 위해서는 부모 노드를 가리키는 배열이 존재해야 합니다.

처음에는 모든 값이 자기 자신을 가리키도록 만듭니다. 

표와 그림으로 그리면 아래와 같습니다.

노드	1	2	3	4	5	6	7	8
노드의 부모	1	2	3	4	5	6	7	8

 

이후 2개의 노드를 연결하면 연결된 노드 중 더 작은 값으로 부모 노드 배열 값을 바꿔줍니다.

만약 1과 2가 연결되었다고 하면 2의 부모 노드 아래와 같이 1로 바뀝니다.

부모의 값이 같아짐으로써 노드들을 합칠 수 있습니다. (Union 알고리즘)

노드	1	2	3	4	5	6	7	8
노드의 부모	1	1	3	4	5	6	7	8

이후 2와 3도 연결하면 다음과 같이 됩니다.

노드	1	2	3	4	5	6	7	8
노드의 부모	1	1	2	4	5	6	7	8

최종적으로 1, 2, 3 모두 연결되어 있는데 1과 3의 부모 노드는 다르기 때문에 연결되어 있는지 알 수 없습니다. 이를 파악하기 위해서는 재귀 함수를 이용합니다. 노드와 노드의 부모 값이 같을 때까지 연결 확인을 반복합니다.

 

Find 알고리즘은 두 개의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘입니다.

 

아래는 Union-Find 알고리즘의 기본 구현 코드입니다. 

#include <stdio.h>

// 부모 노드를 찾는 함수
int getParent(int parent[], int x) {
  if(parent[x] == x) return x;
  return parent[x] = getParent(parent, parent[x]);
}

// 두 부모 노드를 합치는 함수
int unionParent(int parent[], int a, int b) {
  a = getParent(parent, a);
  b = getParent(parent, b);
  if(a < b) parent[b] = a;
  else parent[a] = b;
}

// 같은 부모를 가지는지 확인
int findParent(int parent[], int a, int b) {
  a = getParent(parent, a);
  b = getParent(parent, b);
  if(a == b) return 1;
  return 0;
}

int main(void) {
  int parent[11];
  for(int i = 0; i <= 10; i++) {
    parent[i] = i;
  }
  unionParent(parent, 1, 2);
  unionParent(parent, 2, 3);
  unionParent(parent, 3, 4);
  unionParent(parent, 5, 6);
  unionParent(parent, 6, 7);
  unionParent(parent, 7, 8);
  printf("1과 5는 연결되어 있나요? %d\n", findParent(parent, 1, 5));
  unionParent(parent, 2, 8);
  printf("1과 5는 연결되어 있나요? %d\n", findParent(parent, 1, 5));
}

 

 

 

 

 

 

 

Reference

https://blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)