[알고리즘] Union-Find 알고리즘

Union-Find알고리즘은 서로소 집합, 상호배타적 집합(Disjoint-Set)알고리즘이라고도 불립니다. 여러 노드가 존재할 때, 선택한 두개의 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 입니다.

 

Union-Find 알고리즘에서는 두 노드를 Union연산, 즉 두 노드를 같은 그래프에 합치는 과정과 Find연산, 두 노드가 같은 그래프에 존재하는지를 확인합니다. 

 

위에서와 같인 5개의 서로 연결되지 않은 채로 흩어져 있습니다. 여기서 각 노드들의 연결성을 프로그래밍 적으로 파악하기 위해 1차원 배열을 사용할 수 있습니다. index는 노드, index의 값은 부모노드를 의미합니다. 지금은 모두 독립적으로 존재하기 때문에 부모노드의 값을 현재의 index로 초기화 해줍니다.

 

여기서 두개의 노드가 서로 연결되었다는 것은 부모노드가 같다는 것을 의미합니다. 2번노드와 3번노드를 합치고, 1번노드와 2번노드를 합치면 아래와 같은 모습이 됩니다.

 

근데 1,2,3번 노드은 같은 그래프에 존재하지만 배열에서는 3번 노드의 부모값이 2번노드를 가리키고 있습니다. 2,3번을 먼저 수행했기 때문에 2번노드가 부모가 되지만, 다시 1번 노드가 들어왔기 때문에 이 그래프의 부모노드를 1번이 됩니다. 이렇게 부모가 서로 상이한 과정은 재귀함수로 해결할 수 있습니다. 3번 노드의 부모는 2번인데, 2번노드의 부모는 1번이기 때문에 3번노드의 부모값을 1번노드로 변경해 줍니다.

 

이로써 1,2,3번 노드는 모두 부모노드로 1을 가지고 있기 때문에 같은 그래프에 있다고 할 수 있습니다. 이것이 Union-Find의 전부입니다. 

#include <iostream>

using namespace std;

// n노드의 부모를 반환합니다.
int getParent(int parent[], int n)
{ // n노드의 부모값을 찾음
    if (parent[n] == n)
    {
        return n;
    }
    return parent[n] = getParent(parent, parent[n]);
}

// n1노드와 n2노드의 부모를 합칩니다.
void unionParent(int parent[], int n1, int n2)
{
    n1 = getParent(parent, n1);
    n2 = getParent(parent, n2);
    if (n1 < n2)
    {
        parent[n2] = n1;
    }
    else
    {
        parent[n1] = n2;
    }
}

// n1노드와 n2노드의 부모값이 같은지 확인합니다.
int sameParent(int parent[], int n1, int n2)
{
    n1 = getParent(parent, n1);
    n2 = getParent(parent, n2);
    if (n1 == n2)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int main()
{
    int parent[11];
    for (int i = 1; i <= 10; i++)
    {
        parent[i] = i;
    }
    unionParent(parent, 1, 2);
    unionParent(parent, 2, 3);
    unionParent(parent, 3, 4);
    unionParent(parent, 5, 6);
    unionParent(parent, 6, 7);
    cout << "1과 5는 연결되어 있습니까 ? " << sameParent(parent, 1, 5) << "\n";
    unionParent(parent, 1, 5);
    cout << "1과 5는 연결되어 있습니까 ? " << sameParent(parent, 1, 5) << "\n";

    return 0;
}