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

 

Union-Find 알고리즘은 중복되지 않은 원소들로 이루어진 집합들을 표현할 때 사용하는 알고리즘이다.

아래와 같이 간단하게 구현할 수 있는 자료구조로, 코딩테스트에서는 중복되지 않는 id를 가지는 집들이 있을 때, 거리별로 마을이 만들어진다던가 하는 문제에서 활용하기 좋다.

#include <iostream>
using namespace std;

int parents[11];

void init() {
    for (int i = 1; i <= 10; ++i)
        parents[i] = i;
}

void printOutput() {
    for (int i = 1; i <= 10; ++i)
        cout << parents[i] << " ";
    cout << "\n";
}

int find(int a) {
    if (parents[a] == a)
        return a;
    else
        return parents[a] = find(parents[a]); 
}

void union_(int a, int b) {
    a = find(a);
    b = find(b);

    if (a < b)
        parents[b] = a;
    else
        parents[a] = b;
}

int main() {
    init();
    printOutput();
    union_(1,10);
    union_(10,8);
    union_(2,9);
    printOutput();
    union_(8,2);
    printOutput();

}

출력값은 

1 2 3 4 5 6 7 8 9 10 
1 2 3 4 5 6 7 1 2 1  
1 1 3 4 5 6 7 1 2 1

으로, 1번 노드와 10번 노드, 10번 노드와 8번 노드, 2번 노드와 9번 노드가 합쳐졌을 때 각각 부모노드는 1번, 2번으로 잘 합쳐진 것을 확인할 수 있다.

최종적으로 1번 노드와 연결된 8번 노드를 2번노드와 합쳐 줌으로써 2번 노드의 부모노드도 1번 노드가 되었다.