DisjointSet,Union,Find서로소집합, 상호배타적집합

DisjointSet(상호배타적집합, 서로소 집합)

- 서로 공통된 원소를 가지고 있지 않은 두개 이상의 집합을 말한다.

- DisjointSet data Structure를 사용하면 서로 다른 원소들이 어떤 집합에 속해 있는지를 판단하기에 유용하다.

- 정의에 의해 Disjoint Set 사이에는 교집합이 없기 때문에, 합 연산을 하는 과정에서 두 집합 사이의 겹치는 원소를 특별히 고려하지 않고 모든 원소들을 하나의 집합으로 합치는 것이 가능하다. 이 합하는 과정과 각 원소들이 어떤 집합 속에 있는지 판별하는 과정을 효율적으로 찾기 해서 Disjoint Set Union을 사용합니다.

 

 

DisjointSet은 트리를 이용하여 표현할 수 있습니다.

벡터를 이용한 DisjointSet 트리 구조 표현

 

Union 합치기

 

일반적으로 아래와 같이 합치기 연산을 진행  했을 때는 O(N) 시간 복잡도를 갖게 됩니다.

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

	if (u == v) 
		return;
	
    _parent[u] = v;
}

 

랭크압축(Rank Compression) 통한 최적화

    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]++;  
    }

Find 찾기

 

일반적으로 아래와 같이 소속을 찾는 함수를 구현하게 되면 Find 함수가 호출될 때마다 재귀가 호출되므로 비효율 적입니다

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

        return Find(_parent[u]);
    }

 

경로압축(Path Compression)을 통한 최적화

 

아래와 같이 소속을 찾는 함수가 호출하게 되면 u의 parent를 root parent로 바꿔주는 경로압축을 통해 이후에 호출되는 Find(u) 함수는 빠르게 탐색이 가능하게 됩니다.

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

경로압축

 

Conclusion

- 소속을 합치고, 요소의 해당 소속을 찾는데 적합한 자료구조

- 시간 복잡도 : O(Ackermann(n)) = O(1)

 

PPT