DisJoint Set

1️⃣ Disjoint Set이란?

• Disjoint Set (서로소 집합) 은 공통 원소를 가지지 않는 집합들의 모음을 효율적으로 관리하는 자료구조입니다.
• 주로 네트워크 연결 여부 판별, 최소 스패닝 트리(MST) 생성, 팀 통합 문제 등에 사용됩니다.
• 대표적으로 Union-Find (합치기-찾기) 알고리즘을 통해 집합을 관리합니다.

---

2️⃣ Disjoint Set의 핵심 연산

🔹 초기화 (Initialization)

각 원소는 자기 자신을 부모로 설정 → 독립된 집합으로 시작합니다.

for (int i = 0; i < n; i++)
    _parent[i] = i;

---

🔹 찾기 (Find)

특정 노드가 속한 집합의 대표 노드(루트)를 찾는 연산입니다.

int Find(int u) {
    if (u == _parent[u])
        return u;

    return Find(_parent[u]);  // 루트를 찾을 때까지 재귀 호출
}

---

🔹 합치기 (Union or Merge)

두 개의 집합을 하나로 합치는 연산입니다.

void Merge(int u, int v) {
    u = Find(u);  // u의 루트 찾기
    v = Find(v);  // v의 루트 찾기

    if (u == v) return;       // 이미 같은 집합이면 무시
    _parent[u] = v;           // u 집합이 v 집합 밑으로 들어감
}

---

3️⃣ 최적화 기법: 트리를 더 평평하게!

✅ 경로 압축 (Path Compression)

Find 연산 시 경로를 압축해서 트리의 깊이를 줄입니다.

int Find(int u) {
    if (u == _parent[u])
        return u;

    return _parent[u] = Find(_parent[u]);  // 부모를 루트로 직접 설정
}

💡 효과: 이후의 Find는 O(1)에 가까운 속도로 처리됩니다.

---

✅ 유니온 바이 랭크 (Union By Rank)

병합할 때 트리의 높이가 낮은 집합을 높은 집합 밑으로 붙입니다.

void Merge(int u, int v) {
    u = Find(u);
    v = Find(v);

    if (u == v) return;

    if (_rank[u] > _rank[v])  // 랭크가 큰 쪽을 루트로
        swap(u, v);

    _parent[u] = v;
    if (_rank[u] == _rank[v])
        _rank[v]++;
}

📌 트리의 구조가 균형을 유지하게 되어 성능이 좋아집니다.

---

4️⃣ 시간 복잡도

연산	최적화 X	최적화 O (경로 압축 + 랭크)
Find	O(N)	O(α(N)) ≒ O(1) (아커만 함수)
Merge	O(N)	O(1)

---

5️⃣ 코드 구현

🧱 기본 (Naive) Disjoint Set

class NaiveDisjointSet {
public:
    NaiveDisjointSet(int n) : _parent(n) {
        for (int i = 0; i < n; i++)
            _parent[i] = i;
    }

    int Find(int u) {
        if (u == _parent[u]) return u;
        return Find(_parent[u]);
    }

    void Merge(int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u == v) return;
        _parent[u] = v;
    }

private:
    vector<int> _parent;
};

❌ 단점: 트리의 깊이가 깊어질 수 있음 → 성능 저하

---

⚡ 최적화 Disjoint Set

class DisjointSet {
public:
    DisjointSet(int n) : _parent(n), _rank(n, 1) {
        for (int i = 0; i < n; i++)
            _parent[i] = i;
    }

    int Find(int u) {
        if (u == _parent[u]) return u;
        return _parent[u] = Find(_parent[u]);
    }

    void Merge(int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u == v) return;

        if (_rank[u] > _rank[v])
            swap(u, v);

        _parent[u] = v;

        if (_rank[u] == _rank[v])
            _rank[v]++;
    }

private:
    vector<int> _parent;
    vector<int> _rank;
};

✅ 경로 압축 + 유니온 바이 랭크 최적화 적용 → 거의 O(1)

---

6️⃣ 실전 테스트

int main() {
    DisjointSet teams(1000);

    teams.Merge(10, 1);
    cout << teams.Find(10) << " " << teams.Find(1) << endl;

    teams.Merge(3, 2);
    cout << teams.Find(3) << " " << teams.Find(2) << endl;

    teams.Merge(1, 3);
    cout << teams.Find(1) << " " << teams.Find(2) << " " << teams.Find(3) << endl;

    return 0;
}

🧪 여러 집합을 병합하고 루트 노드가 어떻게 변하는지 확인할 수 있음

---

🎯 Disjoint Set이 쓰이는 곳

• 최소 스패닝 트리(MST) (예: 크루스칼 알고리즘)
• 유니온-파인드 기반 집합 판별
• 네트워크 연결 여부 판단
• 동적 팀 구성 문제
• 게임 서버의 길드/혈맹 관리

---

🧠 아커만 함수란?

• Find 연산의 이론적 시간 복잡도는 O(α(N)) (아커만 역함수)
• 사실상 상수 시간에 가까우므로 대부분 O(1)로 간주함

---