반응형
유니온 파인드(Union - Find)
유니온 파인드란?
- 여러 개의 노드 중 선택된 두 노드가 같은 집합에 속하는지 판별하는 알고리즘
- 서로소 집합(Disjoint - Set) 알고리즘이라고도 불린다.
- 재귀 함수를 이용하여 부모 노드를 찾고, 합친다.
유니온 파인드 실행 과정
- Find
: 선택된 두 노드의 부모를 확인하여 현재 같은 집합에 속하는지 판단하는 과정
- Union
: 두 노드를 합치는 과정. 두 노드를 합쳐서 같은 부모를 가지도록 만든다.
유니온 파인드 코드(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;
}
반응형
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
탐색 알고리즘 - 깊이 우선 탐색(Depth First Search, DFS) (0) | 2020.06.22 |
---|---|
탐색 알고리즘 - 이분 탐색(Binary Search) (0) | 2020.06.22 |
정렬 알고리즘 - 퀵 정렬(Quick Sort) (0) | 2020.06.16 |
정렬 알고리즘 - 병합 정렬(Merge Sort) (0) | 2020.06.16 |
정렬 알고리즘 - 삽입 정렬(Insertion Sort) (0) | 2020.06.14 |
댓글