유니온 파인드 Union-Find C++

개요

Union-Find

데이터 단위를 그룹단위로 나누어 관리하는 알고리즘 Union으로 그룹을 합치고, Find로 찾는 구조이다.

중간에 어떤 노드가 있는지 전혀 궁금하지 않고, 그룹을 합치고, 특정 노드가 어떤 그룹에 속해 있는지 파악하는 것에 초점이 맞혀져 있다.

교집합이 없는 서로소 집합(disjoint set), 그룹을 합치는 것은 있으나 그룹을 쪼개는 것은 없다.

 

Union

일정 노드들을 그룹으로 묶고 부모 노드가 대표가 된다.

Union(1, 2), Union(3, 4), Union(5, 6)

위와 같이 묶은 경우 각 묶음은 하나의 그룹이 된다.

 

Find

단순하게 해당 노드를 찾으라는 의미가 아닌, 해당 노드가 속한 그룹을 찾는다.

 

1. 초기 단계

모든 노드들이 대표인 상태

 

초기 단계

 

노드	1	2	3	4	5	6
부모	1	2	3	4	5	6

 

2. Union 실행

Union(1, 2) => 2번 노드를 1번 노드의 자식으로 묶어라

 

Union 단계

 

노드	1	2	3	4	5	6
부모	1	1	3	4	5	6

 

2번 노드의 부모는 자기 자신에서 1번 노드로 변경이 되었다.

 

Union(3, 4)와 Union(5, 6)을 실행한 경우 아래와 같이 된다.

노드	1	2	3	4	5	6
부모	1	1	3	3	5	5

 

이 상태에서 Union(2, 4)를 하게 되면 4번의 부모 노드가 2번의 부모 노드를 부모로 갖게 된다.

 

 

노드	1	2	3	4	5	6
부모	1	1	1	3	5	5

 

3. Find

재귀적 호출을 통해 해당 노드가 어느 그룹에 속해 있으며, 대표 노드가 무엇인지 까지 알 수 있다.

Find(4)를 할 경우 value로 3번 노드를 반환하고, Find(3)을 수행한다. 이는 value로 1을 반환하고, Find(1)을 수행한다. 입력된 값과 자신이 동일하므로 1번 노드가 대표 노드가 된다.

 

4. 경로 압축 (path compression)

상위 노드를 타고 올라가서 root 노드를 찾는 방식이 아닌, root 노드와 직접적인 연결을 통해 Find 연산 시 시간 복잡도를 줄일 수 있다.

Find 연산 시 root 로드를 찾았을 경우 재귀를 타고 오며 모든 경로에 있는 노드들의 value를 루트 노드로 갱신해 준다.

그럼 이후 Find 연산 시 같은 그룹의 root로드를 빠르게 찾을 수 있다.

 

예제

1. 기본적인 Union과 Find의 형태

#include <iostream>

using namespace std;

int parent[20];

int Find(int a) {
	// 특정 그룹의 대표를 찾는다.
	if (parent[a] == a) return a; // 대표가 자신인 경우
	int root = Find(parent[a]); // root 노드까지 Find
	return root;
}

void Union(int a, int b) {
	// 두 그룹을 합친다.
	int rootA = Find(a); // a노드의 대표 찾기
	int rootB = Find(b); // b노드의 대표 찾기
	if (rootA == rootB) return; // 같은 그룹이면 합칠필요 없음
	parent[rootB] = rootA; // b의 root 노드를 a의 root 노드로 갱신
}

int main() {
	// 1. 자기 자신에 대한 부모화 세팅
	for (int i = 1; i < 20; i++) {
		parent[i] = i;
	}

	// 2. 데이터 저장
	int n, q; // 노드의 개수와 쿼리의 수
	cin >> n >> q;
	for (int i = 0; i < q; i++) {
		int a, b;
		cin >> a >> b;
		Union(a, b); // b를 a 그룹에 속하게 한다.
	}
}

 

2. 경로 압축

Find 함수를 효율적으로 작동하게 한다.

int Find(int a) {
	// 특정 그룹의 대표를 찾는다.
	if (parent[a] == a) return a; // 대표가 자신인 경우
	return parent[a] = Find(parent[a]); // 재귀를 돌아오며 그룹 내 모든 노드들의 value를 root로 갱신
}