Union-Find (Disjoint Set) 자료구조 완전 정복

개요

Union-Find(분리 집합, Disjoint Set Union)는 여러 원소를 분리된 집합으로 관리하는 자료구조입니다. Find(x): x가 속한 집합의 대표 원소 반환, Union(x, y): x와 y가 속한 집합을 합침. 경로 압축과 랭크 기반 합치기를 적용하면 거의 O(1) 수준의 연산이 가능합니다.

---

1. 기본 구현

#include <vector>
#include <numeric>

class UnionFind {
    std::vector<int> parent;
    std::vector<int> rank;

public:
    explicit UnionFind(int n) : parent(n), rank(n, 0) {
        std::iota(parent.begin(), parent.end(), 0); // parent[i] = i
    }

    // 경로 압축 (Path Compression)
    int Find(int x) {
        if (parent[x] != x)
            parent[x] = Find(parent[x]); // 재귀적으로 루트로 직결
        return parent[x];
    }

    // 랭크 기반 합치기 (Union by Rank)
    bool Union(int x, int y) {
        int rx = Find(x), ry = Find(y);
        if (rx == ry) return false; // 이미 같은 집합

        if (rank[rx] < rank[ry]) std::swap(rx, ry);
        parent[ry] = rx;
        if (rank[rx] == rank[ry]) rank[rx]++;
        return true; // 합침 성공
    }

    bool Connected(int x, int y) {
        return Find(x) == Find(y);
    }

    // 집합 크기 추적 버전
};

---

2. 집합 크기 추적

class UnionFindWithSize {
    std::vector<int> parent, sz;

public:
    explicit UnionFindWithSize(int n) : parent(n), sz(n, 1) {
        std::iota(parent.begin(), parent.end(), 0);
    }

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

    bool Union(int x, int y) {
        int rx = Find(x), ry = Find(y);
        if (rx == ry) return false;

        if (sz[rx] < sz[ry]) std::swap(rx, ry);
        parent[ry] = rx;
        sz[rx] += sz[ry];
        return true;
    }

    int Size(int x) { return sz[Find(x)]; }
    bool Connected(int x, int y) { return Find(x) == Find(y); }
};

---

3. 시간 복잡도

연산	기본	경로 압축 + 랭크
Find	O(N) 최악	O(α(N)) ≈ O(1)
Union	O(N) 최악	O(α(N)) ≈ O(1)

α(N)은 역 Ackermann 함수로 실용적으로는 상수입니다.

---

4. Kruskal MST — 최소 신장 트리

#include <algorithm>

struct Edge {
    int u, v, weight;
};

int KruskalMST(int n, std::vector<Edge>& edges) {
    // 가중치 기준 오름차순 정렬
    std::sort(edges.begin(), edges.end(),
        [](const Edge& a, const Edge& b) {
            return a.weight < b.weight;
        });

    UnionFind uf(n);
    int totalWeight = 0;
    int edgeCount = 0;

    for (const Edge& e : edges) {
        if (uf.Union(e.u, e.v)) {
            totalWeight += e.weight;
            edgeCount++;
            if (edgeCount == n - 1) break; // MST 완성
        }
    }

    return totalWeight;
}

// 사용
std::vector<Edge> edges = {{0,1,4},{0,2,3},{1,2,1},{1,3,2},{2,3,4}};
int mst = KruskalMST(4, edges); // 최소 신장 트리 비용

---

5. 사이클 감지

bool HasCycle(int n, const std::vector<std::pair<int,int>>& edges) {
    UnionFind uf(n);

    for (const auto& [u, v] : edges) {
        if (!uf.Union(u, v))
            return true; // 이미 연결됨 → 사이클
    }

    return false;
}

---

6. 게임 개발 활용

6.1 지역 연결 분석

// 맵에서 연결된 지역 그룹 찾기
void FindRegionGroups(const std::vector<std::vector<int>>& map) {
    int rows = map.size(), cols = map[0].size();
    int n = rows * cols;
    UnionFind uf(n);

    auto Index = [&](int r, int c) { return r * cols + c; };

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (map[r][c] == 0) continue; // 빈 칸

            // 오른쪽, 아래 인접 타일과 연결
            if (c + 1 < cols && map[r][c+1] == 1)
                uf.Union(Index(r,c), Index(r,c+1));
            if (r + 1 < rows && map[r+1][c] == 1)
                uf.Union(Index(r,c), Index(r+1,c));
        }
    }

    // 각 그룹의 크기 출력
    std::map<int, int> groupSize;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (map[r][c] == 1)
                groupSize[uf.Find(Index(r,c))]++;
        }
    }
}

6.2 네트워크 연결 상태 관리

// 서버 클러스터 연결 관리
class ServerCluster {
    UnionFindWithSize uf;

public:
    explicit ServerCluster(int n) : uf(n) {}

    void Connect(int server1, int server2) {
        uf.Union(server1, server2);
    }

    bool AreConnected(int s1, int s2) {
        return uf.Connected(s1, s2);
    }

    int ClusterSize(int server) {
        return uf.Size(server);
    }
};

---

정리

• Find: 경로 압축으로 루트까지 직결 → 거의 O(1)
• Union: 랭크(또는 크기) 기반 → 트리 균형 유지
• Kruskal MST, 사이클 감지, 연결 컴포넌트에 핵심 활용
• 동적으로 집합을 합치는 모든 문제에 적용 가능

참고 자료

• cppreference — 관련 알고리즘