유니온 파인드(Union - Find)

유니온 파인드(Union - Find)

 

 

유니온 파인드란?

 

 - 여러 개의 노드 중 선택된 두 노드가 같은 집합에 속하는지 판별하는 알고리즘

 

 - 서로소 집합(Disjoint - Set) 알고리즘이라고도 불린다.

 

 - 재귀 함수를 이용하여 부모 노드를 찾고, 합친다.

 

---

 

유니온 파인드 실행 과정

 

 - Find

  : 선택된 두 노드의 부모를 확인하여 현재 같은 집합에 속하는지 판단하는 과정

 

 - Union

  : 두 노드를 합치는 과정. 두 노드를 합쳐서 같은 부모를 가지도록 만든다.

 

 

 3, 5, 9는 1를 부모 노드로, 7은 2를 부모 노드로 가지고 있고, 나머지는 연결되어 있지 않다.

 

 

노드 3과 노드 6을 합친다.

노드 6의 부모 노드는 6이고, 노드 3의 부모 노드는 1이기 때문에 노드 6의 부모 노드는 1이 된다.

 

노드 2와 노드 3을 합친다.

 

노드 2의 부모 노드는 2이고, 노드 3의 부모 노드는 1이기 때문에 노드 2의 부모 노드는 1이 된다.

 

노드 7의 부모는 2이고, 노드 2의 부모는 1이기 때문에 노드 7의 부모 역시 1이 된다.

 

---

 

유니온 파인드 코드(C++)  

// 유니온 파인드 클래스
class unionFind {
public:
	void initUnion(int n)
	{
		// 부모 노드에 자기 자신이 들어가 있는 경우(아무것도 연결되어 있지 않다.)
		for (int i = 0; i < n; i++)
		{
			parent.push_back(i);
			height.push_back(1);
		}

	}

	int findParent(int node)
	{
		// 노드의 부모가 자기 자신인 경우(최상위 노드, 부모노드)
		if (node == parent[node])
			return node;

		// 노드의 부모를 찾아서 대입한다.
		parent[node] = findParent(parent[node]);

		return parent[node];
	}

	// 노드 두 개 합치기(node1에 node2 붙이기)
	void unionParent(int node1, int node2)
	{
		// node1, node2의 부모 찾기
		node1 = findParent(node1);
		node2 = findParent(node2);

		// 두 노드의 부모 노드가 같다면 아무런 일도 일어나지 않는다.
		if (node1 == node2)
			return;
		// 두 노드의 높이를 비교하여 높이가 큰 노드에 높이가 작은 노드를 연결한다.
		else
		{
			if (height[node1] == height[node2])
			{
				height[node1]++;
				parent[node2] = node1;
			}
			else if (height[node1] > height[node2])
			{
				parent[node2] = node1;
			}
			else
			{
				parent[node1] = node2;
			}
		}

	}

	bool isSameParent(int node1, int node2)
	{
		node1 = findParent(node1);
		node2 = findParent(node2);

		if (node1 == node2)
			return true;
		else
			return false;
	}

private:
	vector<int> parent;

	vector<int> height;

};

 

#include <iostream>
#include <vector>

using namespace std;

// 유니온 파인드 클래스는 위 코드 참조

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	unionFind uf;

	uf.initUnion(10);

	// 1과 3,5,9 노드를 합치기(부모노드 1), 2와 7 합치기(부모노드 2)
	uf.unionParent(1, 3);
	uf.unionParent(1, 5);
	uf.unionParent(1, 9);
	uf.unionParent(2, 7);

	cout << "\n========== 노드 합치기 1  ==========\n\n";
	for (int i = 0; i < 10; i++)
	{
		cout << i << " 의 부모 노드 : " << uf.findParent(i) << endl;
	}

	// 노드 3과 노드 6 합치기
	uf.unionParent(3, 6);

	cout << "\n========== 노드 합치기 2  ==========\n\n";
	for (int i = 0; i < 10; i++)
	{
		cout << i << " 의 부모 노드 : " << uf.findParent(i) << endl;
	}

	// 노드 3과 노드 2 합치기
	uf.unionParent(3, 2);
	cout << "\n========== 노드 합치기 3  ==========\n\n";
	for (int i = 0; i < 10; i++)
	{
		cout << i << " 의 부모 노드 : " << uf.findParent(i) << endl;
	}

	cout << "\n===================================\n\n";
	cout << "노드 3과 노드 7의 부모 노드는 같은가 ? ";
	if (uf.isSameParent(3, 7))
		cout << " Yes " << endl;
	else
		cout << " No " << endl;


	return 0;
}

실행 결과