[자료구조] 분리 집합(Disjoint Set) - 코딩밥상

분리 집합이란?

집합의 정의는 특정 조건에 맞는 원소의 모입입니다.

그 중 분리 집합은 서로 공통된 원소를 갖지 않는, 즉 교집합을 갖지 않는 복수의 집합을 뜻합니다.

따라서 분리 집합에는 교집합이 존재 할 수 없습니다(공집합).

 

때문에 분리 집합은 소속 관계가 분명해야 하는 데이터를 다룰 때 아주 유용합니다.

예들들어 원소 또는 개체가 어느 집합에 소속되어 있는지 정보를 바탕으로 무언가를 하는 알고리즘에 유용합니다.

출처 : 위키 백과

 

---

분리 집합 구현하기

앞 서 살펴본 분리 집합을 트리를 활용하여 구현해 보겠습니다.

주의할 점은 보통의 트리는 부모가 자식을 가리키는 포인터를 갖는 것과 다르게 반대로 자식이 부모를 가리키는 포인터를 갖습니다.

즉 뿌리 노드는 집합 그 자체이고, 뿌리 노드 자신을 포함한 트리 내의 모든 노드는 그 집합의 원소인 것입니다.

 

-분리 집합의 노드 구조체

typedef struct tagDisjointSet{	//노드 구조체
    struct tagDisjointSet* Parent;
    void* Data;
} DisjointSet;

-분리 집합의 기본 연산

분리 집합의 목적은 원소가 어느 집합에 포함되어 있는지 쉽게 알아내는 데에 있습니다. 따라서 우리가 알아야 할 연산은 '합집합'과 '집합 탐색 연산' 단 두가지 입니다.

void DS_UnionSet(DisjointSet* Set1, DisjointSet* Set2){	//합집합 연산
    Set2 = DS_FindSet(Set2);
    Set2->Parent = Set1;
}

앞 서 설명한 성질을 이용하면 아주 쉽게 합집합 연산을 수행할 수 있습니다.

합할 집합의 뿌리 노드를 다른 집합의 뿌리 노드의 부모 노드로 지정하면 됩니다.

 

DisjointSet* DS_FindSet(DisjointSet* Set){	//탐색 연산
    while(Set->Parent == NULL){
        Set = Set->Parent;
    }
    
    return Set;
}

분리 집합의 탐색은 집합에서 원소를 찾는 것이 아니라 원소가 속한 집합을 찾는 연산입니다.

트리의 최상위에 있는 뿌리 노드가 곧 자신이 속한 집합을 나타내므로 Parent가 NULL인 뿌리 노드를 쭉 따라 올라가 찾으면 되겠네요.