[Algorithm] Union Find 알고리즘 (1) (Disjoint Set)

Suh, Hyunwook·2021년 4월 18일
0

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;
}

0개의 댓글