유니온 파인드 (Union Find) 혹은 분리 집합 (Disjoint Set)

유니온 파인드 알고리즘은 같은 집합에 속한 원소들을 O(1)의 시간 복잡도로 확인하는 방법으로 다양한 문제들에서 많이 사용됩니다.

특정 노드는 자신의 부모를 의미하는 P[node] 배열값을 갖습니다.

즉 P[node] = node 인 경우 자기 자신을 부모로 한다는 의미이며, P[node] != node 인경우 다른 노드 번호를 부모로 한다는 뜻입니다. 그럼 대체 이걸 어디에 사용할 수 있을까요?

예를 들어 1번 노드와 3번 노드가 연결되어 있고, 2번 노드와 3번 노드가 연결되어 있다면 1번과 3번이 연결되어있는 것을 알 수 있습니다. 여기서 연결된 노드간 같은 부모를 갖는다고 정의한다면 P[1] = P[2] = P[3] 이며 1 또는 2 또는 3의 값을 가집니다. 편의상 부모 노드의 번호가 작은쪽으로 집합을 생성한다면 P[1] = P[2] = P[3] = 1이 될겁니다.

이는 아래와 같은 코드로 나타낼 수 있습니다.

#include <iostream>
#define MAX (10)
using namespace std;

int parent[MAX];

int getParent(int x) { // x 노드의 부모를 찾자
	if (parent[x] == x) {
		return x;         // 자기 자신이 부모이므로 x 반환
	}
	else {                // 자기 자신이 아니라면
		return parent[x] = getParent(parent[x]); // 자신의 부모의 부모를 찾자
	}
}

void Union(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a < b) { // 노드 번호가 작은것을 부모로 선택한다. 문제 기준에 따라 바꾸면 됨
		parent[b] = a;
	}
	else {
		parent[a] = b;
	}
}

int main() {
	// 자기 자신을 부모로 초기화
	for (int i = 1; i <= MAX; i++) {
		parent[i] = i;
	}
	// 2번 노드의 부모는 ?
	int two_parent = getParent(2);

	// 2번과 1번 노드를 연결 ( 같은 집합으로 만듬 )
	Union(2, 3);
	// 3번과 1번 노드를 연결
	Union(3, 1);

	//새로운 노드의 부모는?
	int new_two_parent = getParent(2);
	cout << two_parent << " -> " << new_two_parent;
}

 

실행 결과

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

11724번 연결 요소의 개수 문제는 BFS, DFS 문제로 보통은 풀지만 유니온파인드를 사용할 수 있습니다. 같은 집합의 부모가 같으므로 중복을 제거하는 set에 부모 노드의 번호를 저장하여 set의 크기를 출력하면서 간단하게 해결 가능합니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <string>
#include <queue>
#include <set>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int n, m;
vector<int> v[1001];
int p[1001];
int gp(int x) {
	if (p[x] == x) {
		return x;
	}
	return p[x] = gp(p[x]);
}
void Un(int a, int b) {
	a = gp(a);
	b = gp(b);
	if (a < b) {
		p[b] = a;
	}
	else p[a] = b;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		p[i] = i;
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		Un(a, b);
	}
	set<int> s;
	for (int i = 1; i <= n; i++) {
		s.insert(gp(i));
	}
	cout << s.size();
}

 

https://www.acmicpc.net/problem/10775

10775번: 공항

1~N 까지 게이트에 비행기가 도킹할 수 있으며, 비행기가 도킹하지 못할 경우 이 때 도킹 가능한 비행기의 최대값을 출력하는 문제입니다.

그리디적인 요소가 들어가는데, 비행기가 댈 수 있는 가장 큰 번호의 게이트에 도킹하는것이 당연합니다.

parent[i]를 1~i번째 게이트에 도킹 가능한 비행기가 현재 시점에서 도킹 가능한 가장 큰 게이트 번호라고 해봅시다. 예를 들어 3번 게이트에 비행기가 도킹되면 3번게이트까지 도킹 가능한 비행기가 도킹할 수 있는 나머지 게이트 중 가장 큰 번호는 2번이므로 Union(getParent(3), getParent(2))를 해주어야 합니다.

여기서 Union(3, 2)가 아니고 getParent(2)를 해주는 이유는, 만약 3번 게이트에 도킹하기 이전에 2번에 다른 비행기가 도킹되어 있는 경우 1~2 번 게이트 중 비행기가 도킹 가능한 가장 큰 번호의 게이트인 parent[2]와 같은 집합을 형성해야하기 때문입니다.

1번 비행기 1~2 도킹 가능

parent[1] = 1, parent[2] = 1, parent[3] = 3

2번 비행기 1~3 도킹 가능

parent[1] = 1, parent[2] = 1, parent[3] = parent[2] = 1

로 업데이트가 되므로 빠르게 도킹 가능한 가장 큰 게이트 번호를 찾을 수 있습니다.

만약 1번 게이트에 다른 비행기가 도킹되어있었다면 parent[1] 이 0으로 갱신되며 getParent(2-1)은 0이므로 더이상 도킹을 할 수 없게 됩니다. 이 시점에서 도킹은 끝나게 됩니다.

#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
int parent[100001];
int getParent(int a) {
	if (a == parent[a])
		return a;
	return parent[a] = getParent(parent[a]);
}
void Un(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a < b)
		parent[b] = a;
	else
		parent[a] = b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	cin >> n >> m;
	for (int i = 0; i <= n; i++)
		parent[i] = i;
	int ans = 0;
	for (; m--;) {
		int node;
		cin >> node;
		int dest;
		if (parent[node] != node)
			dest = getParent(node);
		else
			dest = node;
		if (dest) {
			ans += 1;
			Un(dest, dest - 1);
			continue;
		}
		break;
	}
	cout << ans; 
}

만약 getParent() 함수의 else 에 return getParent(parent[x])를 대신 쓴다면 속도가 현저히 느려집니다.

 

다양한 문제에서도 사용될 수 있는 단순한 알고리즘인 만큼 익혀두면 편할때가 있습니다.