[알고리즘] Union Find

Union Find란?

여러 node들을 묶어 그룹을 만들어내 공통된 조상을 찾는 알고리즘.

작동 방식

초기화

각 node마다 조상의 번호가 부여되어있다.

const int MAX_IDX = 1005;

int root[MAX_IDX];
for(int i = 0;i < MAX_IDX;i++) {
    root[i] = i;
}

node조상 구하기

재귀적으로 조상을 찾는 함수를 호출하여 찾는다. find를 하면서 가장 위 조상을 호출된 node의 조상으로 변경하면 최적화를 할 수 있다.

int union_find(int x)
{
    if (root[x] == x)
        return x;
    return root[x] = union_find(root[x]);
}

node 합치기

조상의 번호를 따라가며 가장 마지막으로 발견되는 조상을 찾아 두 node의 조상을 찾은 조상으로 바꾼다.

// 이 코드는 아래의 union_find 함수를 사용하여 만든 것 이기에
// update를 하지 않는 find 함수에서는 작동하지 않을 수 있다.

void union_join(int a, int b)
{
    int ar = union_find(a);
    int br = union_find(b);

    root[ar] = br;
}

Union Find를 사용한 문제

• 1863번 / 정올
• ydj414의 백준 문제집