유니온 파인드(Union Find)

상호 배타적인 집합을 표현할 때 사용.

유니온 파인드(Unidon Find)란?

정의

유니온 파인드,서로소 집합 알고리즘이라고 하기도 한다.
상호 배타적 인 부분 집합 들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

예시

아래와 같은 원소들이 있다고 가정 했을 때

각각의 원소들이 (1-2, 1-3, 2-4, 5-6, 6-7) 연결 되어있을 때 아래와 같이 3개의 서로소 집합이 나온다.

구현

유니온 파인드 지원 연산

배열과 트리를 이용해서 나타낼 수 있는데 트리를 이용하여 구현 해보겠다.
각 집합의 최상단 노드인 root 노드가 집합을 구분하는 원소가 된다. 즉, 부모 노드 1, 5, 8 이 집합을 구분하는 원소.

parent[i]:원소 i 의 부모노드가 있는 배열, parent[i]의 값은 i의 부모 노드

초기화

• 초기화: 모두 각자 다른 집합이 됩니다. 처음에 각각의 원소들은 연결된 정보가 없기 때문에 부모로 자기 자신을 가지고 있습니다.
• 즉,parent[i]=i;

for(int i=1;i<=n;i++){
	parent[i]=i;
   }

Find(찾기)연산

• 각 노드에 저장된 정보를 따라가 루트 노드를 찾습니다.
• a가 들어오면 루트노드를 확인 합니다.
• root노드가 a(자기자신)일 경우에는 a를 반환하고 아니라면 root를 찾아서 반환 합니다.

int find(int a){
//root인 경우 a를 반환
if(a == parent[a]){
	return a;
    } else{
    //아니면 root를 찾는다
    int p = find(parent[a]);
    parent[a]=p;
    return p;
    }

}

Union(합치기)연산

• 집합의 부모노드(root)를 찾은 뒤 다른 root 노드라면 합칩니다.
• 합치는 방법은 b의 부모 노드를 a의 루트 노드로 설정.

int Union(int a,int b){
a = find(a);
b = find(b);

 if(a != b){
   parent[b]=a;
   }
}

참고한 블로그

https://bowbowbow.tistory.com/26
https://twpower.github.io/115-union-find-disjoint-set