Disjoint set, 분리 집합, Union-Find

disjoint set(분리 집합)이란?

분리 집합: 서로  "중복되지  않는  부분  집합들"로  나누어진  원소들에  대한  정보를 저장하고  조작하는  자료구조
집합을  구현하는  방법은  다양하게  있지만, 보통  트리를  이용해서  구현한다.4

 

 

분리 집합의 구현 (tree)

- 트리 하나가 각각 한 개의 집합을 의미한다. 
- 자식이 부모를 가리키는 방향으로 저장한다. 
- 루트 노드의 부모는 자기 자신을 가리킨다.

 

 

분리  집합의  3가지  연산

 

1.  Make-set(x) : x를 유일한 원소로 하는 집합을 생성한다.

 

2.  Find(x) : x가  속한  집합의  대표값(root node)을  반환한다.
➔  서로  같은  집합인지  다른  집합인지  판단할  때에  쓴다.

3.  Union(x, y) : x가  속한  집합과  y가  속한  집합을  병합한다.

 

3가지 연산 중 우리가 주로 활용할 연산은 Find 연산과 Union연산이다.

그래서 분리 집합을 이용한 문제를 Union-Find 알고리즘 문제라고 부르기도 한다.

 

 

그림을 통해 Union-Find 연산 알아보기

* Find연산은 root node를 반환한다.

Find(1) = 1 Find(2) = 1 Find(3) = 1 Find(4) = 1

Find(5) = 5 Find(6) = 5 Find(7) = 5

 

Union연산

두 집합의 root node 중 하나의 부모를 나머지 하나의 root node로 만들어서 병합한다.

위 그림에서는 파란색 집합의 root node(5)의 부모를 자기 자신에서 초록색 집합의 root node(1)로 바꿔주었다.

 

Union-Find 코드

int Find(int x) {
	if (x == Parent[x]) // root node
    	return x;
    else
    	return Find(Parent[x]);
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    
    Parent[x] = y; // 병합
}

 

 

 

Union Find 코드  최적화

1.  Find 연산에서 최적화 : 경로 압축(Path compression)

root node를 찾기 위한 Find 연산의 횟수를 줄여준다.

 

2. Union 연산에서  최적화  : Union by Rank

 

 
여기에서  rank는  트리의  깊이를  의미하며, 트리의 rank가 작은 집합을 큰 집합 방향으로 union해준다. 
** 트리의 rank가 같은 경우에, 합쳐진 트리의 rank는 1증가

 

최적화 된 코드

int Find(int x) {
	if (x == Parent[x])
    	return x;
    else
    	return Parent[x] = Find(Parent[x]); // 경로 압축
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    
    if (x == y)
    	return;
    
    // union by rank
    if (Rank[x] > Rank[y]) {
    	Parent[y] = x;
    }
    else {
    	if (Rank[x] == Rank[y]) Rank[y]++; // 트리의 rank가 같을 때 1증가
        Parent[x] = y;
    }
}

 

 

분리 집합 문제 풀기

 

1. BOJ 1717 집합의 표현

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

1717번: 집합의 표현

분리 집합의 가장 기본적인 문제이다.

 

코드

#include<iostream>

using namespace std;

int n, m;
int Parent[1000001];
int Rank[1000001];

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

	return Parent[x] = Find(Parent[x]);
}

void Union(int x, int y) {
	x = Find(x);
	y = Find(y);

	if (x == y)
		return;

	if (Rank[x] > Rank[y]) {
		Parent[y] = x;
	}
	else {
		if (Rank[x] == Rank[y]) 
			Rank[y]++;
		Parent[x] = y;
	}
}



int main() {

	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;
	//초기화
	for (int i = 1;i <= n;i++) {
		Parent[i] = i;
		Rank[i] = 0;
	}

	for (int i = 0; i < m; i++) {
		int check, a, b;
		cin >> check >> a >> b;
		if (check == 0) {
			Union(a, b);
		}
		else if (check == 1) {
			(Find(a) == Find(b)) ? cout << "YES\n" : cout << "NO\n";
		}
	}

	return 0;
}

 

 

2. BOJ 20040 사이클 게임

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

20040번: 사이클 게임

 

설명

Union-Find를 이용하면 사이클의 여부를 알 수 있다.

선분을 이었을 때, 사이클이 없다. ➔ 선분을 구성하는 정점 두 개가 다른 집합 안에 있다. 

선분을 이었을 때, 사이클이 생긴다. ➔ 선분을 구성하는 정점 두 개가 같은 집합 안에 있다. 

 

코드

#include<iostream>

using namespace std;

int n, m;
int Parent[1000001];
int Rank[1000001];

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

	return Parent[x] = Find(Parent[x]);
}

bool Union(int x, int y) {
	x = Find(x);
	y = Find(y);

	if (x == y)
		return false;

	if (Rank[x] > Rank[y]) {
		Parent[y] = x;
	}
	else {
		if (Rank[x] == Rank[y]) 
			Rank[y]++;
		Parent[x] = y;
	}
	return true;
}



int main() {

	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;
	//초기화
	for (int i = 0;i < n;i++) {
		Parent[i] = i;
		Rank[i] = 0;
	}
	int cnt = 0, ans = 0;
	for (int i = 0; i < m; i++) {
		cnt++;
		int a, b;
		cin >> a >> b;
		if (!Union(a, b) && ans==0) {
			ans = cnt;
		}
	}
	cout << ans;
	return 0;
}

 

 

3. BOJ 16724 피리 부는 사나이

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

16724번: 피리 부는 사나이

 

설명

지도 밖으로 나가는 경우는 없으므로 항상 사이클이 생긴다.

사이클 중 하나를 Safe zone으로 만들면 된다! ➔ 사이클의 개수 세기

 

코드

#include<iostream>
using namespace std;

int n, m;
int Parent[1000001];
int Rank[1000001];
char board[1001][1001];
bool visited[1000001];

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

	return Parent[x] = Find(Parent[x]);
}

bool Union(int x, int y) {
	x = Find(x);
	y = Find(y);

	if (x == y)
		return false;

	if (Rank[x] > Rank[y]) {
		Parent[y] = x;
	}
	else {
		if (Rank[x] == Rank[y])
			Rank[y]++;
		Parent[x] = y;
	}
	return true;
}



int main() {

	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;
	//초기화
	for (int i = 0;i < n*m;i++) {
		Parent[i] = i;
		Rank[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int nx = i, ny = j;
			if (board[i][j] == 'D') nx++;
			else if (board[i][j] == 'U') nx--;
			else if (board[i][j] == 'R') ny++;
			else if (board[i][j] == 'L') ny--;
			Union(i * m + j, nx * m + ny);
		}
	}
	int ans = 0;
	for (int i = 0;i < n*m;i++) {
		if (!visited[Find(i)]) {
			visited[Find(i)] = true;
			ans++;
		}
	}
	cout << ans;
	return 0;
}

 

 

4. BOJ 16562 친구비

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

16562번: 친구비

 

설명

같은 집합 안에 있는 친구들 중에서 한 명만 친구를 해도 된다.

 ➔  그렇다면 가장 저렴한 친구를 사귀자!!

 

가장 저렴한 친구가 루트 노드가 되도록 union 함수를 수정한다.

 

코드

#include<iostream>

using namespace std;

int n, m, k;
int Parent[100001];
int price[100001];
bool visited[1000001] = {false,};

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

	return Parent[x] = Find(Parent[x]);
}

void Union(int x, int y) {
	x = Find(x);
	y = Find(y);

	if (x == y)
		return;

	if (price[x] > price[y]) Parent[x] = y;
	else Parent[y] = x;

}



int main() {

	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> k;
	//초기화
	price[0] = -1;
	for (int i = 1;i <= n;i++) {
		Parent[i] = i;
		cin >> price[i];
	}
	//유니온
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		Union(a, b);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int tmp = Find(i);
		if (!visited[tmp]) {
			visited[tmp] = true;
			ans += price[tmp];
		}
	}
	(ans > k) ? cout << "Oh no" : cout << ans;
	return 0;
}