[자료구조 / C++] Disjoint Set

Disjoint Set

 

특징

그룹이 있다.

각 그룹은 공통된 요소들이 없다. (상호 배타적)

원소가 어떤 그룹에 속해있는가? (Find)

2개의 그룹을 어떻게 합칠 것인가? (Union) 

 

 

특징에 대한 구체화

그룹이 있다

= 그룹을 특정할 수 있는 "그룹명"은 무엇으로 할까?

= 그룹의 창시자 OR 임의 지정으로 (특정 원소 = 그룹의 상징 = Root)을 만든다.

 

각 그룹은 공통된 요소들이 없다. (상호 배타적)

= 복잡도가 낮다. 

= 오직 하나의 Root를 가지고 있다.

 

원소가 어떤 그룹에 속해있는가? (Find)

= Root를 찾으면 된다. How?

= 최상위 부모까지 올라간다.

= 따로 Root를 저장할 수도 있다. 

 

2개의 그룹을 어떻게 합칠 것인가? (Union) 

= 그룹의 Root를 찾는다.

= Root를 1개로 바꾼다.

 

 

결국 트리로 만들면 쉽다

트리 구조가 쉬운 이유가 몇 가지 있는데

1. Root가 필요하니까

2. Find 연산은 자식에서 부모로 올라가므로 트리 구조가 이상해도(균형이 안 맞아도) 상관없다.

3. Union 연산에서 하나의 그룹을 다른 그룹의 자식으로 넣으면 된다. ( 1번의 포인터 변경 )

트리 구조는 Find, Union가 O(1)의 시간 복잡도를 가진다. (입력 크기에 대해 상수 시간이 소모)

 

구조체 배열로 만들어도 장단점은 있다.

각 원소마다 "최상위 부모"를 저장한다면

Find 연산이 매우 빨라진다는 장점.

Union 연산에서 O(N)이 소모된다는 단점.

 

 

코드

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

class DisjointSet {
public:
    vector<int> parent; 
    vector<int> rank;

public:
    DisjointSet(int size) {
        parent.resize(size);
        rank.resize(size, 0);

        // 각 원소의 부모를 자기 자신으로 초기화
        for (int i = 0; i < size; ++i) {
            parent[i] = i;
        }
    }

    // 원소가 속한 집합의 대표를 찾습니다.
    int findSet(int x) {
        if (parent[x] != x) {
            parent[x] = findSet(parent[x]);
        }
        return parent[x];
    }

    // 두 원소가 속한 집합을 합칩니다.
    void unionSets(int x, int y) {
        int rootX = findSet(x);
        int rootY = findSet(y);

        // 두 집합의 랭크를 비교하여 더 높은 랭크의 집합에 합칩니다.
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            }
            else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            }
            else {
                parent[rootX] = rootY;
                rank[rootY]++;
            }
        }
    }
};

int main(){
    int n = 5; 
    DisjointSet ds(n);

    // 테스트
    ds.unionSets(0, 1);
    ds.unionSets(2, 3);
    ds.unionSets(0, 4);

    for (int i = 0; i < n; ++i) {
        std::cout << "원소 " << i << "가 속한 집합의 대표: " << ds.findSet(i) << std::endl;
    }
    return 0;
}

 

 

Vector<int> rank는 머야

rank는 그룹의 깊이 정보를 저장한다.

이유는 약간의 최적화를 위해서.

 

트리 구조는 균형을 잃거나 깊이가 깊을수록 복잡도가 커지는데

부모에서 자식으로 내려갈 필요가 없다면 균형은 필요 없을 수 있어도

자식에서 부모로 올라가는 연산은 깊이와 관련이 있으므로 깊이 관리가 필요하다.

 

위 코드에서 깊이 관리가 1가지 들어간다.

바로 Union 연산에서 "어떤 그룹이 자식으로 들어갈 것인가?"

더 작은 그룹이 자식으로 들어가면 깊이는 큰 그룹으로 유지된다.