유니온 파인드란?? (Union-Find)

 

 

 

 

유니온 파인드(Union-Find)란 ?

CS에서 서로소 집합을 찾는 기능을 구현하기 위해 중요한 역할을 하며

많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다.

 

(MakeSet으로 각각의 요소를 생성하였다)

 

(union 연산을 수 차례 수행하여 집합을 생성하였다)

출처 : 위키피디아

크게 세 가지 기능으로 분류를 할 수 있다.

 

1. Union

function Union(x, y)           // x와 y를 같은 집합으로 묶는 작업이다. xRoot := Find(x)          // x의 최상단 부모를 찾음 (x의 집합이 어디인가?) yRoot := Find(y)           // y의 최상단 부모를 찾음 (y의 집합이 어디인가?) xRoot.parent := yRoot // x와 y를 묶는다.

 

2. Find

function Find(x)          // Find 작업으로 x의 최상단 부모를 찾는 작업이다. if x.parent == x     // 최상단 부모를 찾았다.

      return x         // bottom-up으로 올라왔기에 이제 return으로 x(최상단 부모) 내려준다       else     return Find(x.parent)    // 아직 못 찾았다 => 재귀적으로 최상단 부모를 찾는다.

 

3. MakeSet

function MakeSet(x)            // 초기화 작업이다.     x.parent := x              // 자신의 부모를 자신으로 설정한다.

// 최상단 부모는 자기자신을 부모로 가진다.

 

 

이제 임의로 작성한 소스코드로 확인을 해보자

소스코드

#include<cstdio>
 
#define MAX 10001
 
int parent[MAX];
 
// x의 최상단 부모를 찾기 (해당하는 집합을 찾기) 
int Find(int x){
    if(parent[x] == x)                    // root를 찾은 경우 
        return x;
    else{                            // 아니면 root를 찾아가야 한다 
        int _parent = Find(parent[x]);
        parent[x] = _parent;
        return _parent;
    }
}
 
// x와 y를 같은 집합으로 묶기 (합 집합) 
// y의 부모를 x의 부모로 저장 
void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    
    if(x != y)
        parent[y] = x;
}
int main(){
    int n;
    scanf("%d",&n);
    
    // parent 초기화 
    for(int i = 0; i <= n; i++){
        parent[i] = i;
    }
    
    while(1){
        int op;
        printf("합치시려면 '0'을 입력하세요.\n");
        printf("확인하려면 '1'을 입력하세요.\n");
        printf("종료하려면 2를 입력하세요.\n");
        scanf("%d",&op);
        if(op == 0){                        // 합치는 연산 
            int a,b;
            printf("합쳐려하는 원소 2개: ");
            scanf("%d%d",&a,&b);
            Union(a,b);
        }
        else if(op == 1){                    // 확인하는 연산 
            int a,b;
            printf("확인하려는 원소 2개: ");
            scanf("%d%d",&a,&b);
            int parent_a = Find(a);                // a의 최상단 부모 
            int parent_b = Find(b);                // b의 최상단 부모 
            if(parent_a == parent_b)            // 두 원소의 최상단 부모가 같다면 같은 집합이다. 
                printf("결괴 : 두 원소는 같은 집합에 해당합니다.\n");
            else
                printf("결과 : 두 원소는 다른 집합에 해당합니다.\n");
        }
        else if(op == 2){                        // 종료하는 연산 
            break;
        }
    }
    return 0;
}

 

 

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.