유니온 파인드(Union-Find)

Disjoint-Set (서로수 집합) 이라고도 불리는 유니온 파인드는 여러 집합이 주어지면 각 집합의 루트 노드가 무엇인지,

또는 Union(합집합) 연산을 손쉽게 하기 위한 일종의 자료구조이다.

 

큰 틀로는 집합의 부모 노드를 찾는 find 함수, 각 집합을 병합하는 union 함수를 만들어주면 된다.

 

int find(int x) {
	if (parent[x] < 0) return x;
	parent[x] = find(parent[x]);
	return parent[x];
}

 

find 함수부터 살펴보면 parent배열의 초기값은 -1로 설정해둔다(이후에 집합의 크기를 알기 쉽게 하기 위해)

만약 parent [x]가 0보다 작다는 소리는 그 노드가 루트 노드임을 알 수 있다.

그대로 x를 반환하면 된다.

 

만약 루트 노드가 아닐경우 재귀적으로 그 노드의 부모 노드를 호출하여 parent [x]에 담는다. 이후 모든 호출이 끝나면 

parent [x]를 리턴해주면 된다.

 

void merge(int x, int y) {
	x = find(x);
	y = find(y);

	if (x != y) parent[y] = x;
}

 

merge는 union연산이다. C언어에서는 union이 이미 사용되고 있기 때문에 union함수명을 사용할 수 없다.

두 집합이 주어지면 그 두 집합의 부모 노드를 찾아서 그 노드가 서로 같지 않다면(같은 집합이 아니라면)

한 노드에 다른 노드를 붙여주기만 하면 된다.

 

백준에서 연습해볼 만한 문제로는

 

www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

집합의 표현이 있다. 문제를 읽어보면 0 ~ n까지 집합을 병합하고

그 집합이 같으면 YES 아니면 NO를 출력해주면 된다.

 

#include <iostream>
#include <vector>
using namespace std;

vector<int> parent;
int n, m, a, b, input;

int find(int x) {
	if (parent[x] < 0) return x;
	parent[x] = find(parent[x]);
	return parent[x];
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);

	if (x != y) parent[y] = x;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;
	parent.resize(n + 1, -1);

	while (m--) {
		cin >> input >> a >> b;

		if (input == 0) merge(a, b);
		else if (input == 1) {
			if (find(a) == find(b)) cout << "YES" << '\n';
			else cout << "NO" << '\n';
		}
	}

	return 0;
}

 

유니온 파인드는 이후 다른 알고리즘에 융합되어 사용된다고 한다.