Union & Find 알고리즘

Union Find란?

서로 중복되지 않는 원소들로 나눠진 부분집합들, 즉 서로소 집합 자료구조인 Disjoint Set을 표현하는 알고리즘이다.

Union Find 메쏘드

Union Find 알고리즘은 Union과 Find라는 2가지 연산으로 이루어진다.
Find(a, b) : a가 어떤 집합에 포함되어 있는지 찾는 연산
Union(a, b) : a와 b집합을 합치는 연산

그림으로 간단하게 알아보기

그림과 같이 1~5까지의 원소가 있다고 생각해보자.
p에 해당하는 값, p[i]는 자기 자신이 어떤 부모(집합)에 포함되어 있는지를 나타낸다.
이 원소들은 처음에 모두 연결되지 않고 자기 자신만을 집합의 원소로 갖고있다.

이 초기화 상태에서 Union(1,2)와 Union(3,4)를 하여 합집합을 만들어보자.

Union(1,2)를 하여 1은 2에 포함되게 되고, Union(3,4)를 하여 3은 4에 포함되는 합집합을 만들었다.

이 상태에서 Union(3,5)를 해보자.

다음 그림과 같이 만들어지는데 여기서 주의해야 할 점은 Union(3,5)를 하였다고 3과 5가 바로 연결되는 것이 아닌, 3의 부모인 4가 5와 연결되었다는 것이다.
즉 Union을 할 때 각 집합을 대표하는 부모끼리 연결이 된다.

이해를 위해 Union(3,2)를 한번 더 해보자.

Union(3,2)를 하게 되면 3의 집합의 부모인 5와 2의 집합의 부모인 2를 연결시켜주게 된다.
즉 1~5원소는 부모가 2인 집합에 속해있다고 말할 수 있다.

하지만 트리 형식으로 구성된 집합이 오른쪽으로 치우쳐져 있다.
지금은 데이터가 5개이지만 데이터가 많아진다면 효율적이지 않게 된다.
따라서 우리는 이 트리를 개선할 수 있다.

어떻게 개선할까?

우리는 Union을 할 때 그 원소가 속한 집합의 부모를 찾기 위해 Find를 한다.
Find를 할 때 재귀호출이 이뤄지는데 그 집합의 부모 노드를 return을 해주어 집합의 원소가 바로 가리킬 수 있게 해준다.

그림으로 살펴보자

이 상태에서 Union(3,2)를 하는 과정에서 Find(3)->Find(4)->Find(5) 재귀호출을 하게되는데 이 때 재귀호출이 끝나고 돌아가는 과정에서 집합의 부모인 5를 return 해주어 p[4] = 5, p[3] = 5로 부모를 갱신시켜 준다.

그 결과 p[4]는 그대로 5일 것이고, p[3]은 5를 가리키는 형태도 갱신된다.
Union(3,2)를 마저 해보자.
3 집합의 부모인 5와 2 집의 부모인 2를 연결시킨다.

최종적으로 이런 형태가 나온다.

알고리즘 개선 전과 후를 비교하면

이렇게 비교가 되는 것을 볼 수가 있다.

코드로 알아보기

#include<iostream>
#include<vector>

using namespace std;

int parent[1001];

int Find(int v) {
	if (v == parent[v])	// 만약 자기 자신이 집합의 부모라면 자신을 return해준다
		return v;

	parent[v] = Find(parent[v]);	//자기 자신이 아니라면 부모를 찾을 때까지 Find를 호출해준다
									//이 때 부모를 찾아 return해줄 때 parent[v]값을 제일 꼭대기에 있는 부모로 갱신해준다
	return parent[v];
}

void Union(int a, int b) {	//a집합과 b집합을 합하는 과정
	a = Find(a);	//a의 부모를 찾아라
	b = Find(b);	//b의 부모를 찾아라

	if (a != b)		//a와 b의 부모가 다르다면	b를 a의 부모에 저장한다.
		parent[a] = b;
}

int main() {

	int N, M, a, b;

	cin >> N >> M;

	for (int i = 1; i <= N; i++) // 1 ~ N까지 원소를 자기 자신으로 초기화 시켜주기
		parent[i] = i;

	for (int i = 1; i <= M; i++) { 
		cin >> a >> b;  
		Union(a, b);  // 두 개의 집합 합치기
	}

	cin >> a >> b;

	int f1 = Find(a);
	int f2 = Find(b);

	if (f1 == f2)
		cout << "YES";
	else
		cout << "NO";

	return 0;
}