[개념] 1.UNION-FIND 유니온파인드 알고리즘

UNION_FIND 알고리즘이란?

합집합 찾기 알고리즘으로, 서로소 집합(Disjoint-Set) 알고리즘이라고도 한다.

여러개의 노드가 존재할 때 두개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

 

*일반적으로 부모를 합칠 때는 더 작은 값 쪽으로 합친다.

 

UNION-FIND에 필요한 함수

- 부모 노드를 찾는 함수 

- 두 부모 노드를 합치는 함수

- 같은 그래프에 속해있는지 확인하는 함수

 

//UNION-FIND
#include<iostream>
using namespace std;
//부모 노드를 가지는 함수
int getParent(int parent[], int idx){
    if(parent[idx]==idx) return idx;
    return parent[idx] = getParent(parent,parent[idx]);
}
//두 부모노드를 합지는 함수
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;
}
// 같은 그래프에 속하는지 검사하는 함수
bool checkParent(int parent[], int a, int b){
    a = getParent(parent, a);
    b = getParent(parent, b);
    if(a==b) return true;
    else return false;
}
 
int main(){
    int arr[10];
    for(int i=1; i<10;i++){
        arr[i]=i;
    }
    unionParent(arr, 1,2);
    unionParent(arr, 2,3);
    unionParent(arr, 3,4);
    unionParent(arr, 5,6);
    unionParent(arr, 7,8);
    unionParent(arr, 8,9);
 
    cout<<"1과 2는 같은 집합에 속하는가요?"<<checkParent(arr,1,2);
 
}

**나동빈님 강의 정리하면서 공부한 내용입니다.

https://youtu.be/AMByrd53PHM

|본 포스팅은 쿠팡 파트너스의 일환으로 소정의 수수료를 제공받을 수 있음을 알립니다 |