[C++] 유니온 파인드(Union-Find)

핵심 요약

 

• 유니온 파인드는 그래프 탐색으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.
• 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다.
• 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어진다.
• 트리 구조로 이루어진 자료구조 중 한가지로 생각되기도 한다.

 

 

연산

 

1. Find - 노드 x가 어느 집합에 포함되어 있는지 찾는 연산
2. Union - 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산

 

 

예제 코드

 

#include <iostream>
using namespace std;

int parent[9]; //배열에 해당하는 것

int find (int x){
	if (parent[x]== x) return x; //배열 인덱스와 값이 같다면 해당 값 리턴
	return parent[x]= find(parent[x]); //배열의 값을 인덱스로 갖는 값 리턴
}

void union(int x,int y) {
	x= find(x);
	y= find(y); //각각 find연산을 통해 루트 노드를 가짐
    
	if (x== y) return; //x와 y가 같다면 이미 연결되어있는 것
    
	parent[y]= x; //배열의 y인덱스에 x값을 저장
}

bool isUnion(int x,int y) {//두 노드가 연결되어있는지 판별하는 함수
	x= find(x);
	y= find(y);
    
	if (x== y) return true;
	return false;
}

int main() {
	for (int i= 1; i<= 8; i++) //배열 초기화 과정
		parent[i]= i;

	union(1, 2); //{1, 2}, {3}, {4}, {5}, {6}, {7}, {8} 
	union(4, 5); //{1, 2}, {3}, {4, 5}, {6}, {7}, {8} 
	union(5, 6); //{1, 2}, {3}, {4, 5, 6}, {7}, {8} 
    
	cout<< "2와 4는 같은 집합인가?\n"<< isUnion(2, 4)<< "\n";// false
    
	union(1, 5); //{1, 2, 4, 5, 6}, {3}, {7}, {8}
	cout<< "2와 4는 같은 집합인가?\n"<< isUnion(2, 4)<< "\n";// true
    
	return 0;
}