유니온파인드(Union-Find)에 대해 알아보자

혼자 공부삼아 끄적끄적...

참고한 블로그는 https://blog.naver.com/ndb796/221230967614 입니다. 좋은 내용 감사합니다.

1. Union-Find 이란?

  - 대표적인 그래프 알고리즘입니다.

  - 서로소 집합 (Disjoint-Set) 그리고 병합 찾기 집합 (Merge-Find-Set), 합집합 찾기(Union-Find) 이라고도 부릅니다.

  - 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 서로 같은 집합에 속하는지 판별하는 알고리즘입니다.

2. Union-Find 연산

  ① 초기화

    - 특정한 노드의 부모를 찾을 수 있도록 만들어 준다.

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

  

  ② 합하기

    - 두 부모 노드를 합친다.

 void 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;
    } else {
        return 0;
    }
 } 

3. Union 과정

  ① 여러개의 노드들이 자신만의 하나의 집합의 원소로 가지고 있습니다.

노드번호	1	2	3	4	5	6	7
부모노드번호	1	2	3	4	5	6	7

  ② unionParent(1,3)을 통해 각 노드들의 부모를 찾고 합친다.

노드번호	1	2	3	4	5	6	7
부모노드번호	1	2	1	4	5	6	7

  ③ unionParet(5, 6)을 통해 각 노드들의 부모를 찾고 합친다.

노드번호	1	2	3	4	5	6	7
부모노드번호	1	2	1	4	5	5	7

  ④ Union(3,4) 을 하게되면, 4의 부모는 3이 되지만 재귀적으로 실행하기 때문에 3의 부모인 1을 결국 가리키게 됩니다.

    

노드번호	1	2	3	4	5	6	7
부모노드번호	1	2	1	1	5	5	7

  ⑤ 이러한 과정에 걸쳐 아래와 같이 구성되어 있다고 하고 코드를 통해 알아보겠습니다.

노드번호	1	2	3	4	5	6	7
부모노드번호	1	1	1	1	5	5	5

4. Union-Find 구현 

  - 위의 예제 처럼 main 함수에서 uinonParent를 통해 노드들을 구성하였습니다.

  - 그리고 출력화면으로 findParent를 통해 현재 같은 집합에 속해있는지 확인할 수 있으며 

    0을 반환하면 false 이므로 같은 집합이 아니고, 1을 반환한다면 true로 같은 집합이라고 볼 수 있습니다.

 #include <stdio.h>
 
 
 //부모 노드를 찾는 함수 
 int getParent(int parent[], int x) {
     if(parent[x]==x) {
         return x;
     } else {
         return parent[x] = getParent(parent, parent[x]);
     }
 } 
 
 // 두 부모 노드를 합치는 함수
 void 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;
    } else {
        return 0;
    }
 } 
 
 int main(void) {
     int parent[7];
     for(int i=1; i<7; i++) {
         parent[i]=i;
     }
     
     unionParent(parent, 1, 3);
     unionParent(parent, 2, 3);
     unionParent(parent, 5, 6);
     unionParent(parent, 3, 4);
     unionParent(parent, 1, 2);
     unionParent(parent, 5, 7);
     printf("1과 5 : %d\n", findParent(parent, 1, 5));
     printf("1과 2 : %d\n", findParent(parent, 1, 2));
     printf("2와 3 : %d\n", findParent(parent, 2, 3));
 
 }

▶ 결과화면

- 결과화면으로 1과5는 다른 집합이고, 1과 2, 3은 같은 집합이라는 결과를 확인할 수 있습니다.