서로소 집합(Disjoint set), 유니온 파인드(Union-Find tree)

(출처: 종만북)

상호 배타적 집합(=서로소 집합, Disjoint Set)을 표현할 때 사용되는 유니온 파인드(Union-Find) 자료구조를 알아봅시다.

 

 

서로소 집합이란?

집합 사이 공통 원소가 없는(=상호배타적인) 집합을 서로소 집합이라 말합니다.

 

Fig 1. 서로소 집합이 아닌 예시

Fig 1.은 6의 약수와 8의 약수를 집합으로 나타낸건데 교집합이 있으니 서로소 집합이 아닙니다.

 

Fig 2. 서로소 집합의 예

Fig 2.는 생일 월에 따라 나눈 집합입니다. 1월생이면서 2월생일 수 없으니 서로소 집합이라고 할 수 있습니다.

 

 

유니온 파인드(Union-Find tree)

서로소 집합들로 이루어진 원소들의 정보를 저장하고 조작하기 위한 자료구조가 유니온 파인드 자료구조입니다. 합치기(union) 연산과 찾기(find) 연산을 지원해 유니온-파인드라고 종종 부릅니다. 가~끔 유파라고 줄여서 쓰는 사람도 봤습니다.

 

Fig 2.처럼 학교에서 생일 월이 같은 사람끼리의 집합들을 만들려고 합니다. 이를 표현하기 위해서는 각 사람을 0부터 n-1의 원소로 나타낸 뒤, 각 1개의 원소를 포함하는 n개의 집합을 만듭니다. 두 사람 a와 b의 생일 월이 같다는 게 확인되면 두 사람이 포함된 집합을 합칩니다.

이를 구현하기 위해서는 아래 연산들이 필요합니다.

• 초기화: n개의 원소가 각각의 집합에 포함되어 있도록 초기화합니다
• 합치기(union) 연산: 두 원소 a, b가 주어질 때 이들이 속한 두 집합을 하나로 합칩니다
• 찾기(find) 연산: 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환합니다

 

(1) 가장 간단한 방법

1차원 배열을 하나 이용하면 가장 간단하게 서로소 집합을 표현할 수 있습니다. 다음과 같은 배열을 하나 만듭니다.

\[belongsTo[i] = \text{i번 원소가 속하는 집합의 번호} \]

처음에 belongsTo를 각자 다른 숫자(belongsTo[i]=i)로 초기화 하면 크기가 1인 n개의 집합을 만들 수 있습니다.

이 경우 찾기 연산은 O(1)의 시간이 걸리지만, 합치기 연산은 배열의 모든 원소를 순회해야 하기 때문에 O(n)의 시간이 걸립니다.

 

(2) 단순한 구현

트리를 사용하면 서로소 집합을 표현할 수 있습니다. parent 배열을 만든 뒤 (1)과 동일하게 parent[i]=i로 초기화 한 뒤, find, union 연산을 각각 구현합니다.

• find: 원소가 포함된 트리의 루트를 찾은 뒤 이들이 같은지 비교합니다
• union: 각 트리의 루트를 찾은 뒤, 하나를 다른 한쪽의 자손으로 넣습니다

struct NaiveDisjointSet {
	vector<int> parent;
	NaiveDisjointSet(int n) : parent(n) {
		for (int i = 0; i < n; ++i)
			parent[i] = i;
	}

	// u가 속한 트리의 루트 번호를 반환
	int find(int u) const {
		if (u == parent[u]) return u;
		return find(parent[u]);
	}

	// u가 속한 트리와 v가 속한 트리를 합친다
	void merge(int u, int v) {
		u = find(u);
		v = find(v);

		if (u == v) return;	// 이미 같은 트리에 속하는 경우
		parent[u] = v;	// u가 속한 트리를 v 밑으로
	}
};

C++에서는 union이 예약어이기 때문에 merge로 썼습니다.

find와 merge가 트리의 높이에 비례하는 시간이 걸려 O(n)이었던 배열 구현보다는 나은 것 같지만, 한쪽으로 기울어진 트리(skewed tree)가 되어버린 경우 find, merge 둘 다 O(n)이 되어버립니다.

 

(3) 최적화된 구현

유니온 파인드의 최적화 방법중 두가지를 적용해봅시다.

• 경로 압축(path compression): find(u)를 호출할 때 u가 속하는 트리의 루트를 찾아내 parent[u]를 찾아낸 루트로 바꿈
• 랭크에 의한 합치기(union-by-rank): 두 트리를 합칠 때 항상 높이가 더 낮은 트리를 더 높은 트리 밑에 집어넣음
  --> 트리의 높이가 h-1가 되기 위해 최소 x개의 노드가 필요하다고 하면, 높이가 h가 되기 위해서는 최소 2x개의 노드가 필요함
  --> 트리의 높이는 포함한 노드 수의 로그에 비례
  --> O(lgN)

struct OptimizedDisjointSet {
	vector<int> parent, rank;
	OptimizedDisjointSet(int n) : parent(n), rank(n, 1) {
		for (int i = 0; i < n; ++i)
			parent[i] = i;
	}

	// u가 속한 트리의 루트 번호를 반환
	int find(int u) {
		if (u == parent[u]) return u;
		return parent[u] = find(parent[u]);	// 경로 압축
	}

	// u가 속한 트리와 v가 속한 트리를 합친다
	void merge(int u, int v) {
		u = find(u);
		v = find(v);

		if (u == v) return;

		// union-by-rank
		// 작은 트리를 큰 트리 밑에 넣음
		if (rank[u] > rank[v]) swap(u, v);
		parent[u] = v;

		if (rank[u] == rank[v]) ++rank[v];
	}
};

두 최적화를 적용한 경우 찾기와 합치기 모두 O(1)로 간주할 수 있습니다.

정확히 쓰면 \(O(\alpha(N))\)으로, 에커만 함수(Ackermann function)의 역함수가 됩니다.

에커만 함수는 엄청나게 빠르게 증가하기 때문에 \(\alpha(n)=5\)가 되는 첫 번째 n은 대략 \(2^{2^{65536}}\)의 값이 됩니다. 따라서 상상할 수 있는 거의 모든 크기 n에 대해 4 이하의 값이 되고, 현실적인 모든 입력에 대해 상수 시간에 동작한다고 봐도 됩니다.

path compression이나 union-by-rank 둘 중 하나만 적용하면 O(log N)의 시간복잡도를 갖습니다.

 

union-by-rank를 적용하기 전에는 merge할 때 무조건 v밑에 u 트리를 넣는데, union-by-rank를 적용하면 merge할 때 루트가 u가 될수도, v가 될수도 있는 점 염두해야 합니다.

 

 

연습문제

• 백준 1717: 집합의 표현
• 백준 2463: 비용