알고리즘 문제 해결 전략 2 6장 트리 (9)

25 상호 배타적 집합

25.1 도입

상호 배타적 집합

이렇게 공통 원소가 없는, 다시 말해 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조가 바로 유니온-파인드 자료 구조임. 

 

배열로 상호 배타적 집합 표현하기

belognsTo[]. 찾기 연산이 O(1)이라는 점이 아주 좋음. 합치기 연산을 빠르게 하려면?

 

트리를 이용한 상호 배타적 집합의 표현

트리의 루트에 있는 원소를 각 집합의 대표. 모든 자식 노드가 부모에 대한 포인터를 가지고 있어야 함. 

struct NaiveDisjointSet {
	vector<int> parent;
	NaiveDisjointSet(int n):parent(n) {
		for (int i = 0; i < n; i++)
			parent[i] = i;
	}
	int find(int u) const {
		if (u == parent[u]) return u;
		return find(parent[u]);
	}
	void merge(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return;
		parent[u] = v;
	}
};

 

상호 배타적 집합의 최적화

두 트리를 합칠 때 항상 높이가 더 낮은 트리를 더 높은 트리 밑에 집어넣음으로써 트리의 높이가 높아지는 상황을 방지하는 것이 필요함. 

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

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

	void merge(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return;
		if (rank[u] > rank[v]) swap(u, v);
		parent[u] = v;
		if (rank[u] == rank[v]) ++rank[v];
	}
};

간단하면서도 아주 큰 효과가 있는 또 다른 최적화. 이 최적화는 찾기 연산이 중복된 계산을 여러 번 하고 있다는데 착안함. 경로 압축(path compression)최적화라고 부름. 상호 배타적 집합이 하는 일은 많은 경우 그래프나 다른 자료 구조로도 할 수 있지만, 구현이 매우 간단하고 동작 속도가 아주 빠르기 때문에 다른 알고리즘의 일부로 사용되는 경우가 많음. 

 

예제: 그래프의 연결성 확인하기

 

예졔: 가장 큰 집합 추적하기

집합들이 합쳐지는 과정에서 가장 큰 집합의 크기가 어떻게 변하는지 추적한다거나, 과반수를 출현하는 시점을 찾는다거나 하는 작업을 간단하게 구현할 수 있음. 

 

25.2 문제: 에디터 전쟁

댓글 정보가 주어질 때 이 댓글 정보 중 모순되는 것은 없는지 확인하고, 모순되는 것이 없을 때 한 파티의 가능한 최대 인원을 계산하는 프로그램을 작성하시오. 

 

25.3 풀이: 에디터 전쟁

ack(), dis() 함수는 각각 모순을 확인한 뒤. 

akc(), dis()의 수행 시간은 모두 merge()와 find()가 지배함. 이 문제의 실질적인 시간 복잡도는 초기화와 maxParty()의 수행 시간에 드는 O(n)의 시간에, 각 연산을 처리하는 데 걸리는 O(m)의 시간을 더해 O(n+m)이 됨.

struct BipartiteUnionFind {
	vector<int> parent, rank, enemy, size;
	BipartiteUnionFind(int n) :parent(n), rank(n, 0), enemy(n, -1), size(n, 1) 
	{
		for (int i = 0; i < n; i++) parent[i] = i; 
	}
	int find(int u) {
		if (parent[u] == u) return u;
		return parent[u] = find(parent[u]);
	}
	int merge(int u, int v) {
		if (u == -1 || v == -1) return max(u, v);
		u = find(u); v = find(v);
		if (u == v) return u;
		if (rank[u] > rank[v]) swap(u, v);
		if (rank[u] == rank[v]) rank[v]++;
		parent[u] = v;
		size[v] += size[u];
		return v;
	}
	bool dis(int u, int v){
		u = find(u); v = find(v);
		if (u == v) return false;
		int a = merge(u, enemy[v]), b = merge(v, enemy[u]);
		enemy[a] = b; enemy[b] = a;
		return true;
	}
	bool ack(int u, int v){
		u = find(u),v = find(v);
		if (enemy[u] == v) return false;
		int a = merge(u, v), b = merge(enemy[v]);
		enemy[a] = b;
		if (b != -1)enemy[b] = a;
		return true;
	}

	int maxParty(const BipartiteUnionFind& buf) {
		int ret = 0;
		for (int node = 0; node < n; ++node) {
			if (buf.parent[node] == node) {
				int enemy = buf.enemy[node];
				if (enemy > node) continue;
				int mySize = buf.size[node];
				int enemySize = (enemy == -1 ? 0 : buf.size[enemy]);
				ret += max(mySize, enemySize);
			}
		}
		return ret;
	}
};