Disjoint Set - Union Find

 

Union-find : 합치기-찾기.

 

이 알고리즘은 예로들어 어떤 배열에서. 어떤 인덱스에 접근해보았더니 그 원소가 가진 값이 이 인덱스의 부모.

즉 나와 연결고리를 찾는 과정. -> 최고 부모가 누구인지(Find). 혹은 내가 원한다면 다른 원소와의 연결고리를 합치는(Union) 알고리즘.

 

이 구조를 단순히 배열만을 이용한다면

찾는과정은 바로 찾을 수 있겠지만, 합치기 과정에서 모든 배열을 순회하면서. 합쳐야할 원소를 찾아야 한다.

 

그렇기에 트리 구조를 통한 Union-Find의 표현을 본다.

트리 구조를 통한 Union-Find의 첫번째 특징은.

 

먼저 Union-Find를 하기전에 모든 노드가 자기자신을 가리킨다.

즉. 처음에는 자기자신이 연결된 노드간의 꼭대기. 루트노드라고 보는것.

class UnionFind
{

public:
	UnionFind() = delete;
	UnionFind(int n) : m_parent(n)
	{
		int i;
		for (i = 0; i < n; ++i)
			m_parent[i] = i; // 모두 자기자신을 가르킴.
	}
private:
	vector<int> m_parent; // 간단하게 배열로 표현가능 (힙트리구조를 배열로 표현한것과 같음)

};

 

즉. 배열을 통해. 자기자신의 인덱스와 같은 원소값으로 초기화를 진행하였고.

 

나중에 Union을 통해 연결고리가 만들어진다. 예로들면

3번과 5번의 인덱스는 자기 자신인 3,5를 들고있다. Union과정에서 이 둘이 각각 3번은 1번을. 5번은 3번을 가리키게 된다면 연결고리는 [5] -> [3] -> [1]이 되는것. 즉 인덱스 [1] = 1. [3] = 1. [5] = 3. 이게 된다.

 

즉. 나중에 보았을 때. 5번이나 3번이나 타고들어가면 1번이 최고 부모인 것을 알게되고 이 셋은 서로 연결되어있다는 것도 알 수 있게된다.

최고 부모(꼭대기)의 특징은 자기 자신의 원소가 인덱스와 같은 값을 가진다는 것. (혹은 연결고리가 없거나)

 

어떤 값 두개가 누가 최고 부모인지 알고 싶다면(서로 연결이 되어있는지 알고싶다면).

재귀적으로 두 원소가 인덱스값과 같은지 타고 들어가면서 같은 값을 내뱉는지만 확인하면 된다.

int Find(int u)
{
	// 나 자신이 최고 부모였다. 바로 리턴.
	if (u == m_parent[u])
		return u;

	return Find(m_parent[u]);
}

 

또 예를 들어보면

[1]        [6]

[3]        [9]

[5]        [2]

[7]        [8]

 

7과 8이 연결되어 있는지 확인하고싶다면 Find메소드를 통해 재귀적으로 최고 부모가 같은지 확인해보면

7은 1과 연결되어있고. 8은 6과 연결되어있으니 서로 연결되어 있지 않다는것을 알 수 있다.

 

이제 Union(합치기)을 본다.

// u와 v를 합친다. 
void Union(int u, int v)
{
	//최고 부모를 찾는 과정.
	u = Find(u);
	v = Find(v);

	// 둘이 같은 그룹(연결고리)라면 무시.
	if (u == v)
		return;

	// 서로 같은 연결고리가 아님.
	m_parent[u] = v;
}

하지만 이 과정은 조금 비효율적이다.

 

왜냐하면 합치는 과정에서 예로들어 [1][3][5][7][9][10][11][15]... 이렇게 합쳐졌고. 15와 11의 최고 부모를 찾는다면 맨 끝에서 하나하나씩 타고 올라가면서 최고 부모를 찾아야하기에. 결국 리스트(선형 시간복잡도)와 다를바가 없다.

 

그렇기에 이 Union 하는 과정을 최적화 시켜보면

트리 구조로 연결된 노드들을. 서로 최고 부모가 달라 합치는 과정이 발생한다면.

높이가 낮은 트리를 높이가 더 높은 트리에게 합치는 것. -> Union By Rank라고 함.

 

이것도 예를 들어보면.

[1]               [4]

[2]             [5][8][7]

[3]                [9]

                   [10]

 

두 트리를 합치면 왼쪽의 트리를 오른쪽의 트리쪽으로 붙여주는 것.

 

class OptimizedUnionFind
{

public:
	OptimizedUnionFind() = delete;
	OptimizedUnionFind(int n) : m_parent(n), m_rank(n, 1) 
	{
		int i;
		for (i = 0; i < n; ++i)
			m_parent[i] = i;
	}

	// 
	int Find(int u)
	{
		// 나 자신이 최고 부모였다. 바로 리턴.
		if (u == m_parent[u])
			return u;

		return Find(m_parent[u]);
	}

	// u와 v를 합친다. (큰 값이 더 작은값에 속하게한다->정해진 규칙은아님)
	void Union(int u, int v)
	{
		u = Find(u);
		v = Find(v);

		// 둘이 같은 그룹(연결고리)라면 무시.
		if (u == v)
			return;

		// 서로 같은 연결고리가 아님.
		m_parent[u] = v;
	}


private:
	vector<int> m_parent;
	vector<int> m_rank; // 멤버변수추가.
};

 

랭크라는 동적배열 멤버가 추가가 되었다.

 

우선 Union을 수정해본다면

void Union(int u, int v)
	{
		u = Find(u);
		v = Find(v);

		// 둘이 같은 그룹(연결고리)라면 무시.
		if (u == v)
			return;

		if (m_rank[u] > m_rank[v])
			swap(u, v);

		// 여기까지 온다면 m_rank[u] <= m_rank[v]가 보장이된다.


		// 서로 같은 연결고리가 아님.
		m_parent[u] = v;

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

랭크의 값의 비교와 (트리의 높이)

같다면 rank의 값을 증가시키는 코드를 실행하고 있다.

 

예로들어 Union(3,5)가 들어왔다고 보자.

(서로 부모는 자기자신)
그럼 u와 v는 다시 3,5로 find를 리턴할 것이고.

 

랭크간의 비교를 해본다. 처음에 모두 트리의 높이가 1로 초기화가 되어있으니.

if문은 무시가 되고.

 

인덱스 3의 원소는 3에서 5로 수정이 된다 -> m_parent[3] = 5, m_parent[5] = 5.

그리고 두 트리의 높이는 같았으니. 최고 부모인 5의 트리는 3을 포함하여 높이가 2가 된 것.

 

랭크간의 비교를 하여 swap을 하는 이유는. 더 높은 트리에게 붙이기 위함이고.

 

마지막 if문에서 두 트리의 높이가 같다면 ++하는 이유도. 예로들어

[1]     [3]

[2]   [4][5]

          [6]

의 두 트리를 합치면 왼쪽 트리가 오른쪽 트리에 붙어서. 

     [3]

  [4][5][1]

     [6][2]

가 될것이다. 즉 더 높은 트리의 높이가 똑같이 유지가 된다는 것. (최고 부모를 가리키므로 작은 트리의 최고 부모는 더 높은 트리의 최고 부모 바로 자식으로 위치)

 

하지만 두 트리의 높이가 같다면?

[1]     [3]

[2]   [4][5]

[3]      [6]

 

합치게 된다면

     [3]

   [4][5][1]

      [6][2]

         [3]

이렇게. 트리의 높이가 4! 가 되었으므로 두 트리의 높이가 같을 때. m_rank++를 해주는 것.

 

이것으로 Union의 최적화는 마쳤지만. Find도 최적화가 가능하다.

int Find(int u)
{
	// 나 자신이 최고 부모였다. 바로 리턴.
	if (u == m_parent[u])
		return u;

	return m_parent[u] = Find(m_parent[u]);
}

Find함수는 결국 어떤 값을 넘기면. 그 최고 부모가 누구인지 찾는 함수이다.

 

즉 

[1] : 1

[3] : 1

[5] : 3

[10] : 5

식으로 연결되어있는 트리가 있다면. 결국 모두가 1이라는 최고 부모를 찾는 것.

그렇기에. 애초에 연결을 해놨다면. 그 원소에 바로 위 부모를 저장하지말고. Find를 하면서 최고 부모의 값을 저장해주는 것.

 

즉 저 위의 연결고리를

[1] : 1

[3] : 1

[5] : 1

[10] : 1

로 바꿔주자는 것이다.

 

이렇게하면 매번 타고타고 들어가 최고 부모를 찾는 과정이 불필요해지고. 한번 저렇게 바꾸어놓았다면.

O(1)의 시간복잡도를 가지게 된다. (기존 방법이었다면 트리의 높이 - 시작 위치만큼 연산을 함)