Union-Find 알고리즘

Disjoint Set

Disjoint Set이란, 서로 중복되지 않는 부분 집합(서로소 집합)들로 나누어진 것을 의미한다.

집합을 구현하는 방법은 벡터, 배열, 연결리스트 등을 이용할 수 있으나 가장 효율적인 트리 구조를 이용하여 표현한다.

 

Union Find

Disjoint Set을 표현할 때 사용하는 알고리즘이 Union Find 알고리즘이다.

◎ Union(x, y)

-> x가 속한 집합과 y과 속한 집합을 합치는 연산을 수행한다

◎ Find(x)

→ x가 속한 집합의 대푯값을 반환하는 연산을 수행한다. x가 어떤 집합에 속해 있는지 찾아주는 연산으로

트리를 이용해서 구현하는 방법이 대부분이므로 대푯값은 루트 노트 번호를 의미한다

 

알고리즘의 진행상황을 처음부터 그림으로 한 번 살펴보자면

① 초기 상태

처음에는 모두 자기 자신이 루트 노드를 가지는 즉, 자기 자신이 대푯값인 집합을 생성이 된다.

index	1	2	3	4	5	6
Parent[ ]	1	2	3	4	5	6

 

위 사진처럼 알파벳 A,B,C,D,E가 모두 자신의 집합 대표값인 모습으로 초기화 시키는 것이다.

void Init_Parent(int Parent[], int N){
	for(int i=1;i<=N;i++) 
    	Parent[i] = i;
}

위 코드처럼 나타낼 수 있다.

 

그리고 부모 노드를 찾고자 하는 함수를 작성해주어야 하는데, 이는 재귀적으로 수행하는 함수를 만들게 된다.

int getParent(int x) {
	if (Parent[x] == x) return x;
	return Parent[x] = getParent(Parent[x]);
}

 

② 두 개의 집합을 Union하고자 할 때 ( 두 개의 집합 합치는 연산 )

이제 두 개의 집합을 합치는 연산을 수행하고자 한다.

원래는 각각이 독립된 상태로 자기 자신이 대표값인 상태였지만 두 개의 집합을 합치고자 한다면 두 집합을

하나의 대표값으로 나타내주어야한다. 보통 트리에서는 최소값이 루트 노드에 오도록 구현하기 때문에

부모값이 작은 값으로 대표값을 설정해준다.

위 그림은 Union(1,2)를 수행해준 모습이다. 원래는 모두 독립된 상태였지만, 1,2집합을 합치는 과정에서

대표 노드값이 더 작은 1의 밑으로 2가 들어간 모습이다. 이렇게 되면 대표값 1을 가지는 집합 안에

노드값 1과 2가 존재하게 되는 것이다.

 

위 그림에서 Union(3,4)을 다시 한 번 수행하게 되면 아래와 같은 모습이 된다.

void UnionParent(int a, int b) {
	int na = getParent(a);
	int nb = getParent(b);
	if (na < nb) 
		Parent[nb] = na;
	else if(na > nb)
		Parent[na] = nb;
}

Union함수는 위 처럼 작성할 수 있다. a의 대표노드값을 찾고, b의 대표 노드값을 찾는다.

그리고 더 작은 노드값을 가지는 집합의 대표값으로 집합의 대표값을 변경해주는 것이다. 

 

③ 대표 노드값으로 같은 집합인지 확인하기

집합의 Union과정이 끝났으면, 같은 집합의 경우 트리 형태로 대표노드값을 집합의 최소값으로 가지게 된다.

그럼 같은 집합인지 확인하려면? 트리의 대표노드값을 확인했을 때 같은 값이라면 두 원소는 같은 집합에 있다는 것을 의미하고, 다른 대표노드값이라면 두 원소는 같은 집합이 아니라는 것을 의미한다.

위에서 부모 노드(대표 노드값)을 반환하는 함수를 만들었기에 이 부분은 그 함수를 사용하면 된다.

bool Is_Same_Parent(int a, int b) {
	int pa = getParent(a);
	int pb = getParent(b);

	if (pa == pb) return true;
	return false;
}

 

위 알고리즘은 다양한 코딩 테스트에서 출제가 되고 있고, 저번에 경험해본 SCPC 1차 문제에서도 나왔던 출제빈도가 낮지 않은 알고리즘이다. 

관련 문제로는 아래 문제들이 있다.

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

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

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

1717번: 집합의 표현

 

 

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>
#define INF 987654321
#define CUNLINK ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define endl '\n'

using namespace std;

int N, M;
int Parent[1000003];

int getParent(int x) {
	if (Parent[x] == x) return x;
	return Parent[x] = getParent(Parent[x]);
}

void UnionParent(int a, int b) {
	int na = getParent(a);
	int nb = getParent(b);
	if (na < nb) 
		Parent[nb] = na;
	else if(na > nb)
		Parent[na] = nb;
}

bool Is_Same_Parent(int a, int b) {
	int pa = getParent(a);
	int pb = getParent(b);

	if (pa == pb) return true;
	return false;
}

int main() {
	CUNLINK;
	cin >> N >> M;
	for (int i = 0; i <= N; i++) Parent[i] = i;
	while (M--) {
		int Check, a, b;
		cin >> Check >> a >> b;

		if (!Check) {
			if (a == b) continue;
			UnionParent(a, b);
		}
		else {
			if (a == b) cout << "YES" << endl;
			else {
				if (Is_Same_Parent(a, b)) cout << "YES" << endl;
				else cout << "NO" << endl;
			}
		}
	}
	return 0;
}