union find 알고리즘 상세정리

유니온 파인드 알고리즘은 2개의 노드를 합치는 과정입니다.

union find ( 합침, 찾음 ) 을 뜻하는 말이죠.

일단 모든 노드는 각자의 소속을 가지고 있습니다. 소속 = 집합.

초기에는 각 집합에는 자기 자신밖에 없죠.

이제 한녀석이 다른 녀석들을 필요에 의해서 하나씩 하나씩 union하기 시작합니다. (가중치가 작은 간선을 선택하면 kruskal 알고리즘)

그리고 그 합쳐지는 녀석이 자신의 집합에 속하는지 find 합니다.

보통 이런관계를 트리로 표현합니다.

그 집합의 주인을 최종 root node로 놓고 연결해 나가는 것이죠.

1개의 트리는 1개의 집합이 됩니다.

그렇기 때문에 노드가 어떤 집합에 존재하는지의 여부는 그 노드가 속한 집합의 최종 부모인 

root node를 찾으면 되겠습니다.

만약 root node가 같다면 그 노드는 같은 집합(트리)에 속한 것이 됩니다.

코드를 통해서 살펴보도록 하겠습니다.

아래 코드는 나동빈님 블로그 https://m.blog.naver.com/ndb796/221230967614 를 참고 하였습니다.

/*

유니온 파인드는

해당 노드가 같은 트리에 포함되어 있는지 체크하는 알고리즘이다.

노드2개의 촤상위 부모의 노드가 같으면 바로 같은 트리에있는 구조라고 할 수 있다.

즉, 같은 트리에 속하는 여부는 "너와 나의 기원이 같니"라는 질문과 동일하다.

*/

#include <iostream>

#include <cstring>

#include <cstdlib>

using namespace std;

int getParent(int parent[], int x);

void unionParent(int parent[], int a, int b);

int findParent(int parent[], int a, int b);

int main(){

//freopen("input.txt","r",stdin);

int parent[11]; // 총 11개의 노드의 부모를 표시합니다.

for(int i=0; i<11; ++i){

parent[i] = i; // 처음에 각자의 부모는 각자가 되도록 설계한다.

}

/*간선가중치가 작은대로 순서대로 추가.*/

/*추가하면서 union find로 같은 사이클인지 체크.*/

/*union find는 2개의 노드의 최종 부모를 찾아서 같은 트리(집합)인지 비교해서 판단*/

unionParent(parent,1,2); // 정보를 추가합니다. 1과 2중 더 작은 노드를 부모로하여 부모자식관계를 만듭니다.

unionParent(parent,2,3); // ..

unionParent(parent,3,4);

unionParent(parent,5,6);

unionParent(parent,6,7);

unionParent(parent,7,8);

cout<<findParent(parent,1,2)<<"\n"; //노드 1과 2가 같은 부모를 가지는지 검사합니다. 1이 나오겠죠?

cout<<findParent(parent,3,5)<<"\n"; //위 정보에따르면 3의 부모는 2, 2의 부모는 1이고 5의 부모는 자기자신이므로 같은 집합(트리)에 속하지 않기때문에,

//0을 출력할 것입니다.

return 0;

}

int getParent(int parent[], int x){ // 최종 부모를 추출하는 함수.

if(parent[x] == x) return x; // x의 부모가 x자신이면 최종부모이므로 반환. (초기에 모든 노드의 부모를 자기 자신으로 주었음.)

return parent[x] = getParent(parent, parent[x]); // 만약 부모의 노드와 자신이 다르면, 부모가 있는 것이므로, 재귀

}

void unionParent(int parent[], int a, int b){ // a,b를 합친다.

a = getParent(parent, a); //a의 최종 부모를 get

b = getParent(parent, b); //b의 최종 부모를 get

if( a<b ) parent[b] = a; // b의 부모가 a보다 크면 ( 노드 순서는 작은 녀석이 더 우위에 있도록 약속 )

// b의 부모를 a로 만듬

else parent[a] = b; // vise versa

}

int findParent(int parent[], int a, int b){ // a,b가 같은 부모를 가지는지 (같은 트리내에 있는지) 확인

a= getParent(parent,a);

b= getParent(parent,b);

if(a==b) return 1; // 같은 부모이면 a,b중 1개를 새로 추가하면 사이클이 생긴다.

else return 0;

}

이제 이 union find알고리즘을 활용하여 kruskal알고리즘을 배워보도록 하겠습니다.