Union Find 알고리즘
임의의 두 Node가 동일한 '상호배타적인 집합(Disjoint Set)'에 속하는 지 판별하는 알고리즘
결론부터 말하자면, 그래프 내에 Cycle이 존재하는 지 여부를 판별하고, Cycle이 존재하면 비효율적인 것으로 판단하여, 최소 연결로 '낭비'를 줄이는 알고리즘이라고 볼 수 있다.
이 결론에 도달하기 위해서, 먼저 Union Find의 원리를 살펴보도록 한다.
Union Find에서는 보스-부하 관계를 가져서 이해하면 좋은데, 초기에 각 노드들은 자기 자신이 최종보스이고, 그룹의 개수는 8개이다. 배열의 Index는 부하로, 배열의 Value는 최종보스를 기입한다. 현재 각 그룹의 보스는 자기자신이므로, 이는 '0'으로 표현한다.
이러한 초기 세팅에서,
"A ← B, B ← C, C ← D, E ← F, F ← G, G ← H"로 Union을 맺고, 이를 화살표로 표현하면 다음과 같다.
Union을 맺은 뒤에는, 최종 보스는 2명, 그룹은 2개로 줄었다. C,D는 B와 달리, 자신의 직속보스가 최종보스는 아니지만, 한 그룹 내 최종보스를 공유하며, 하나로 연결되었다. 즉, 공동보스가 난립하지 않고 (=Cycle 존재하는 상황), 한 명의 최종보스 밑에 그룹을 형성하였다.
그럼 최종보스를 찾는 것은 어떻게 설정할까? 이는 재귀(Recursion)와 Direct Addressing Table 개념을 사용하여, 구현할 수 있다. 예를 들어, D의 경우 C가 보스(Value)이지만, 재귀의 다음 Level에서는 C를 Index로 넘겨주어, 최종보스인 A (= Value가 0)인 값까지 이동한다. 말보다는 소스코드로 보는 것이 이해하기가 쉬울듯하다.
#include <iostream>
using namespace std;
char arr[100];
int groupcnt = 8;
int getBoss(char tar) {
if (arr[tar] == 0) return tar; // 0이라면 (=최종보스라면) 그 값의 index를 return
char ret = getBoss(arr[tar]); // 0 아니면, 최종 찾을때까지 재귀
return ret; // 최종보스 다 찾았으면? ret(=tar)을 밑에 setUnion함수로 return 시키기
}
void setUnion(char t1, char t2) {
char a = getBoss(t1); // a의 최종보스를 받아오세요!
char b = getBoss(t2); // b의 최종보스를 받아오세요!
if (a == b) return; // 이미 그룹이 맺어있다면 끝내세요!
else arr[b] = a; // 그게 아니라면, b(부하)의 최종보스는 a입니다
groupcnt--; // Union 맺을때 마다 group 감소
}
int main()
{
//A~D까지 연결하기
setUnion('A', 'B');
setUnion('B', 'C');
setUnion('C', 'D');
//E~H까지 연결하기
setUnion('E', 'F');
setUnion('F', 'G');
setUnion('G', 'H');
// 문제1. 두 Node가 같은 그룹입니까?
if (getBoss('A') == getBoss('I')) cout << "같은 그룹";
return 0;
// 문제2. setUnion 이후 그룹은 몇 개인가?
cout << groupcnt;
}
그럼, 한 노드와 같은 그룹에 있는 구성원(노드)의 숫자는 어떻게 구할까? 이는 해당 노드의 최종보스를 구하고, Union을 맺을 때, 일종의 장치를 걸어주어 구할 수 있다. 소스코드는 다음과 같다.
#include <iostream>
using namespace std;
char arr[100];
char buhaCnt[100]; // 각 index를 Node로 볼 때, 거느리고 있는 부하의 수
char getBoss(char tar)
{
if (arr[tar] == 0) return tar;
char ret = getBoss(arr[tar]);
return ret;
}
int getCount(char tar) {
char a = getBoss(tar);
return buhaCnt[a];
}
void setUnion(char t1, char t2)
{
char a = getBoss(t1);
char b = getBoss(t2);
if (a == b) return;
arr[b] = a;
buhaCnt[a] = buhaCnt[a] + buhaCnt[b];
buhaCnt[b] = 0;
// 부하인 b의 구성원 수를 흡수하고, b를 초기화해버린다.
}
void init() {
for (int i = 0; i < 100; i++) buhaCnt[i] = 1;
}
int main()
{
init(); //모든 부하를 1로 초기화
setUnion('A', 'B');
setUnion('B', 'C');
setUnion('C', 'D');
setUnion('E', 'F');
setUnion('F', 'G');
setUnion('G', 'H');
for (int k = 0; k < 8; k++) {
char ch;
cin >> ch;
cout << getCount(ch) << '\n';
}
// 각 노드마다 구성원의 숫자를 출력하기
return 0;
}