[자료구조] 분리 집합(Disjoint set)과 유니온 - 파인드(Union-Find)

분리집합?

 

분리집합이란 서로소 집합이라고도 불립니다.

 

이름에서도 알 수 있듯,

 

각각의 집합이 공통 원소를 가지지 않는 집합입니다.

 

즉 전체 집합 U에 두 개의 집합 A, B가 있을 때

 

A ∩ B = Ø 가 성립됩니다,.

이는 집합이 두 개가 아닌 세 개 이상이여도 마찬가지로, 각각의 집합이 공통원소를 가지지 않습니다.

 

 

Union - Find

 

이러한 분리집합의 구현과 연산은 Union - Find로 이루어집니다.

말 그대로, Union(병합), Find(찾기) 인데요.

 

두 개의 트리셋 A와 B가 있다고 합시다.

 

A와 B의 자식노드들은 모두 루트(최상위 노드)를 가리키고 있습니다.

그렇다면, 이 트리 두개를 병합하려면 어떻게 해야 할까요?

 

바로 B의 루트가 A의 루트를 가리키게 하면 됩니다.

 

각 트리셋의 자식 노드가 루트(최상위 노드)를 찾는 과정이 Find,

한 트리셋의 루트가 다른 트리셋의 루트를 가르키게 하여 트리를 병합하는 과정이 Union 입니다.

 

 

 

코드로 구현

먼저, n개의 원소가 있다고 가정했을때, 그들의 부모를 저장할 배열 parent가 필요합니다.

int[] parent = new int[n];

 

 

 

find(x)

find는 자식 노드에서 최상위 노드를 찾는 과정입니다.

x와 x의 부모가 같다면 x를 리턴,

그렇지 않다면 재귀적으로 find를 수행합니다.

 

int find(int x) {
	if (x == parent[x]) return x;
	return parent[x] = find(parent[x]);
}

 

 

union(x,y)

union은 트리를 병합하는 과정입니다.

위에서 만든 find로 각 트리의 부모 노드를 찾고, 같지 않을 경우 부모를 어느 한 쪽에 붙입니다.

 

주어진 문제의 내용에 따라, 부모 중 누가 더 크냐를 비교하여 최적화를 할 수도 있지만,

본 포스팅은 알고리즘 설명이므로 누가 더 큰지 비교는 생략하고 같은지, 같지 않은지만 비교하도록 하겠습니다.

 

void union(int x, int y) {
	int nx = find(x);
	int ny = find(y);
	if (nx != ny) {
		parent[nx] = ny;
	}
}

 

 

 

후기

위 알고리즘으로 예제를 풀어보길 원하신다면, 아래 포스팅을 참고해주시기 바랍니다,

 

https://uknowblog.tistory.com/43

[백준 1043번][Kotlin] 거짓말 (분리집합, Union-Find 사용)

 

https://uknowblog.tistory.com/56

[백준 1717번] [Kotlin] 집합의 표현

 

 

 

자료구조중 하나인 분리 집합, 그리고 분리집합을 표현하기 위한 유니온 - 파인드 알고리즘 이였습니다.

 

최소 스패닝 트리로 처음 접했던 알고리즘인데,

 

최소 스패닝 트리 외에도 쓰이는 곳은 꽤 만더군요.

 

생각보다 문제에 자주 나와서, 매번 같은 설명을 적으려니 지쳐서(...) 한 번 글로 작성해 보았습니다.

 

위 설명만으로 이해가 안된다면 예제를 한 번 풀어보시기 바랍니다.