Union-Find (Disjoint Set)

Disjoint Set

서로소 집합(Disjoint Set)은 서로 겹치지 않는 집합을 말합니다. 즉, 두 집합의 교집합이 공집합인 경우를 의미합니다. 프로그래밍에서 서로소 집합은 주로 Union-Find를 통해 구현되며 거의 같은 의미로 사용됩니다. 유니온-파인드는 어떤 원소 \( x \)가 속한 집합을 \( O(1) \)에 찾고, 두 집합을 합치는 연산을 효율적으로 처리할 수 있는 자료구조입니다.

예를 들어, 1번과 2번이 같은 집합에 속해 있고, 3번과 4번이 같은 집합에 속해 있습니다. 여기서 1번과 3번을 같은 집합으로 합치면 결과적으로 1, 2, 3, 4가 모두 같은 집합에 속해있게 됩니다. 유니온-파인드는 이름처럼 union과 find 두 가지 연산을 지원합니다.

Find: 어떤 원소가 속한 집합을 찾는 연산입니다. 예를 들어, find(1)을 호출하면 1번이 속한 집합의 대표(루트) 원소를 반환합니다.
Union: 두 원소가 속한 집합을 합치는 연산입니다. 예를 들어, union(1, 3)을 호출하면 1번과 3번이 속한 집합을 하나로 합칩니다.

구현

유니온-파인드는 트리 처럼 표현됩니다. 각 원소는 부모 원소를 가리키며, 만약 부모가 없는 루트 원소라면 자기 자신을 가리킵니다. \( N \)개의 원소가 있을 떄, parent 배열을 통해 각 원소의 부모를 저장합니다. 일단 처음에는 모든 원소가 자기 자신만으로 이루어진 집합에 각각 속해 있으므로 parent[i] = i로 초기화합니다. 지금 parent 배열은 다음과 같습니다. (\( N = 5 \))

0 1 2 3 4

여기서 1이 0과 같은 집합에 속하고, 2는 1의 밑에 속하며, 3, 4가 같은 집합에 속하도록 합친다고 해 보겠습니다. 실제로는 union 연산을 통해 수행됩니다. 지금은 union 연산을 구현했다고 가정하고 합쳐진 모습을 보겠습니다.

이런 구조인 경우 2의 부모는 1, 1의 부모는 0입니다. 0과 3은 루트 노드이므로 parent 배열에서 자기 자신을 가리킵니다. 따라서 parent 배열은 다음과 같습니다.

0 0 1 3 3

find 연산은 어떤 원소가 속한 집합의 루트 노드를 찾습니다. find(2)를 호출하면 루트인 0을 반환합니다. 이 과정은 재귀적으로 부모를 따라 올라가면서 수행됩니다.

int find(int x) {
    if (parent[x] == x) {
        return x; // 루트 노드인 경우
    }
    return find(parent[x]); // 부모를 따라 올라감
}

이 find 연산을 사용하면 어떤 두 원소가 같은 집합에 속해 있는지 확인할 수 있습니다. 만약 같은 집합에 속해 있다면, 같은 루트를 가질 것이므로 find(a) == find(b)로 확인할 수 있습니다. 참고로, find 연산을 이렇게 구현하면 시간복잡도가 \( O(N) \)이 됩니다. 그래서 최적화를 위해 경로 압축(Path Compression) 기법을 사용합니다. find 연산의 목적은 결국 루트 노드를 찾는 것입니다. 위 그림에서 2가 1의 밑에 있어서 2에서 출발해 1을 거쳐 0까지 올라가야 했습니다. 경로 압축은 find 연산을 수행할 때, 그 노드를 루트 노드의 바로 밑에 붙이는 기법입니다. 루트 노드만 알면 되기 때문에 중간 노드들을 모두 루트 노드에 바로 연결하는 것입니다. 코드로는 다음과 같이 구현됩니다.

int find(int x) {
    if (parent[x] == x) {
        return x; // 루트 노드인 경우
    }
    return parent[x] = find(parent[x]); // 경로 압축 적용
}

이렇게 하면 대부분의 경우 \( O(1) \)에 find 연산을 수행할 수 있습니다.

다음은 union 연산입니다. union은 사실 굉장히 간단하게 구현할 수 있습니다. 현재 parent 배열이 다음과 같은 모습이라고 해 봅시다.

여기서 union(1, 3)을 호출합니다. 단순하게 1의 루트 노드와 3의 루트 노드를 찾아서 하나를 다른 쪽에 붙이면 됩니다. 대부분 유니온 파인드는 같은 집합에 속해 있는지만 알면 되기 때문에 어떤 원소가 루트 노드가 되던 크게 상관없습니다. 따라서 어떤 노드가 루트가 될 지는 크게 신경쓰지 않아도 됩니다. 코드로 구현하면 다음과 같습니다.

C/C++에서 union은 이미 예약된 키워드이므로 다른 이름을 사용해야 합니다.

void unite(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);

    if (rootA != rootB) {
        parent[rootB] = rootA; // rootB를 rootA에 붙임
    }
}

이제 union(1, 3)을 호출하면 parent 배열은 다음과 같이 변합니다.

유니온 파인드는 이게 전부입니다. 백준 1976번: 여행 가자 문제를 통해 실제로 구현해 보겠습니다. 이 문제는 \( N \)개의 도시를 여행하는 계획이 주어졌을 때 이 계획이 가능한지를 확인하는 문제입니다. 예를 들어 어떤 도시 A에서 B로 가야할 때 어떤 경로를 통해서라도 A에서 B로 갈 수 있다면 계획이 가능한 것입니다. 즉, 서로 이어진 도시들끼리 같은 집합에 속해 있다고 볼 수 있습니다. 따라서 유니온-파인드를 사용하여 서로 연결된 도시들을 같은 집합으로 묶고, 여행 계획에 있는 도시들이 모두 같은 집합에 속해 있는지 확인하면 됩니다.

#include <bits/stdc++.h>

using namespace std;
void fio() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); }

int parent[201];
int n, m;

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

void unite(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa != pb) {
        parent[pb] = pa;
    }
}

int main() {
    fio();

    cin >> n;
    cin >> m;

    for (int i = 0; i <= n; i++) {
        parent[i] = i;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            if (x == 1) {
                unite(i + 1, j + 1);
            }
        }
    }

    bool ok = true;
    int prev; cin >> prev;
    for (int i = 0; i < m - 1; i++) {
        int cur; cin >> cur;
        if (find(prev) != find(cur)) {
            ok = false;
            break;
        }
        prev = cur;
    }

    if (ok) cout << "YES";
    else cout << "NO";
}

Union-Find (Disjoint Set)

Disjoint Set

구현

연습문제