[C++ 자/알 Note] Disjoint Set

집합이 필요한 경우

모든 유저들이 팀번호를 부여받는 경우를 생각해 보자

이러한 경우에서 유저 클래스에 teamId가 있을 것이다

그리고 팀 동맹 기능이 추가된 경우에 아래와 같이 코드를 작성할 수 있다

찾기 연산은 빠르지만 합치기 연산은 O(N)이 문제가 된다

이러한 경우에 집합을 사용하면 효율적이다

void Example()
{
	struct User
	{
		int teamId;
		// TODO
	};

	// TODO : UserManager
	vector<User> users;
	for (int i = 0; i < 1000; i++)
	{
		users.push_back(User{ i });
	}

	// 예시 1) 팀 동맹
	// users[1] <-> users[5]
	users[5].teamId = users[1].teamId; // 1

	// 예시 2) teamId==1인 팀과 teamId==2인 팀이 동맹
	for (User& user : users)
	{
		if (user.teamId == 1)
			user.teamId = 2;
	}

	// 찾기 연산 O(1)
	// 합치기 연산 O(N)

}

 

집합 관련 개념

집합과 뒤에 나오는 개념을 위해서는

아래에서 작성한 개념을 보는 것이 좋다 

https://motivelessstudy.tistory.com/536

 

Disjoint Set

Disjoint Set은 상호배타적 집합을 의미한다

이러한 개념을 이용해서 맨 처음 발생한 예시를 고친다면

아래와 같이 코드를 작성할 수 있고

시간복잡도는 트리의 높이에 비례하게 되며 훨씬 효율적이다

class NaiveDisjointSet
{
public:
	NaiveDisjointSet(int n) : _parent(n)
	{
		for (int i = 0; i < n; i++)
			_parent[i] = i;
	}

	int Find(int u)
	{
		if (u == _parent[u])
			return u;

		return Find(_parent[u]);
	}

	void Merge(int u, int v)// u와 v를 합친다 (u가 v 밑으로)
	{
		u = Find(u);
		v = Find(v);

		if (u == v)
			return;

		_parent[u] = v;
	}

	// 시간 복잡도 : 트리의 높이에 비례한 시간이 걸림
	// [1]		[3]
	// [2]	 [4][5]
	//			[0]

private:
	vector<int> _parent;
};

 

Disjoint Set 경로압축과 랭크기반 알고리즘

위에서 만든 DisjointSet의 아쉬운 점이 있다

1) Find 및 Merge를 하는 경우에

트리가 한쪽으로 치우쳐진 경우라면 시간복잡도가 오래 걸린다는 것이다

2) 두 트리를 Merge를 하는 경우에

어떤 트리를 어떤 트리 밑으로 오게끔 해야 하는지에 대한 최적화가 필요하다

 

1번의 해결법은

Find가 발생할 때마다 트리의 높이를 낮춰줄 수 있는 경로압축 작업을 해주면 된다

그렇게 하기 위해서는 재귀적으로 parent를 설정해 주면 된다

 

2번의 해결법은

항상 높이가 낮은 트리를 높이가 높은 트리 밑으로 오게끔 하는

Union-By-Rank기반 알고리즘을 적용하면 높이가 더 커지지 않는다

 

이 두 가지 최적화가 적용된 코드는 아래와 같고

시간복잡도는 find와 merge 모두 O(1)된다

참고로 이해를 위해 merge라고 함수명을 작성했지만

실제로는 union이라고 함수명을 작성하는 것이 일반적이다

class DisjointSet
{
public:
	DisjointSet(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;

		//_parent[u] = Find(_parent[u]);
		//return _parent[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);

		// rank[u] <= rank[v] 보장
		_parent[u] = v;

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

	// 시간 복잡도 O(Ackermann(n)) = O(1)
	// [1]		[3]
	// [2]	 [4][5][0]

private:
	vector<int> _parent;
	vector<int> _rank;
};