[알고리즘 트레이닝] 6장 - 유니온-파인드 자료구조

유니온-파인드 자료구조(Union-find structure)

🧭 유니온-파인드 자료 구조(Union-find structure)란?

• 집합의 묶음을 관리하는 구조인데, 여기서 말하는 집합은 서로소 집합(disjoint set)입니다. 즉, 하나의 원소가 둘 이상의 집합에 속하지 않습니다.
• 이 집합을 가진 자료구조에 대해 union 연산은 두 집합을 합치는 연산이고, find 연산은 주어진 원소가 포함된 집합의 대푯값(부모 노드)을 구하는 연산입니다. O(log n) 시간에 동작한다고 알려져 있습니다.

대푯값 4와 대푯값 2를 가지는 각각의 disjoint set

대푯값 4의 집합을 대푯값 2의 집합으로 합쳤을 때의 상황

• 두 집합을 합칠 때, 원소가 더 적은 집합의 대푯값을 많은 집합의 대푯값으로 연결하는 전략을 보통 채택합니다.

🧭 유니온-파인드 자료 구조 구현하기

이 자료구조는 배열을 사용하여 편하게 구현할 수 있습니다.

• link 배열 : 각 원소에 대해 경로상의 다음 원소를 저장하는 배열. 원소가 대푯값인 경우, 배열에 저장되는 값은 자기 자신이 됩니다.
• size 배열 : 각 대푯값에 대해 집합의 크기를 저장하는 배열.

맨 처음에는 각 원소가 모두 별개의 집합이라고 가정하고 다음과 같이 초기화합니다.

1
2

for(int i = 1; i<=n; i++) link[i] = i;
for(int i = 1; i<=n; i++) size[i] = i;

• find 함수 : 원소 x의 대푯값을 반환하는 함수. x에서 시작하는 경로를 쭉 따라가면 됩니다.

1
2
3
4
5

int find(int x) {
    while (x!= link[x])
        x = link[x];
    return x;
}

• same 함수 : 두 원소 a, b가 같은 집합에 속하는지 확인하는 함수. find 함수를 활용합니다.

1
2
3

bool same(int a, int b){
    return find(a) == find(b);
}

• unite 함수 : 원소 a와 b가 속한 집합을 합치는 함수로, 이 두 원소 a,b 는 다른 집합에 속해 있어야 합칠 수 있습니다. 이 함수에서는 먼저 두 집합의 대푯값을 구한 다음, 작은 사이즈의 집합의 대푯값을 큰 집합의 대푯값으로 연결합니다.

1
2
3
4
5
6
7
8

void unite(int a, int b){
    a = find(a);
    b = find(b);
    if (size[a] < size[b])
        swap(a, b);
    size[a] += size[b];
    link[b] = a;
}

• 경로 압축 : find 연산을 구현할 때, 한 번 find 연산을 실행 시 경로상의 모든 원소가 대푯값을 바로 가리키도록 할 수 있는 구현 방법을 말합니다. 추후에 탐색 시간 복잡도를 줄일 수 있는 효과적인 방법입니다.

1
2
3
4

int find(int x){
    if (x == link[x]) return x;
    return link[x] = find(link[x]);
}

Disjoint-set 문제

• 백준 : 4195번 - 친구 네트워크 (https://www.acmicpc.net/problem/4195)