Disjoint Set(분리집합)

1. 분리집합

분리 집합은 서로소 집합이라고도 합니다. 용어의 의미처럼 분리 집합은 다음과 같은 특징을 가집니다. 전체집합 U에 대해, U의 분리 집합 A, B는 다음 조건을 만족합니다.

• A, B는 U의 부분집합입니다.
• A, B는 공통 원소를 가지지 않습니다.
• A, B의 합집합이 곧 전체집합 U입니다. (A, B에 속하지 않는 U의 원소가 없어야 합니다.)

※ 이는 분리 집합의 개수가 3개 이상일 때도 동일하게 적용됩니다.

즉, 이미 존재하는 집합 U에 대해 겹치는 부분이 발생하지 않도록 모든 원소들을 분리한 부분집합을 말합니다.

그럼 분리집합을 트리구조로 어떻게 만들 수 있을까? 답은 간단합니다. 자식노드가 부모노드를 가리키게 만들면 됩니다. 그럼 루트노드는 자식노드를 얼마든지 만들 수 있고, 그 부모자식 노드들이 하나의 집합을 이룬다고 보면 됩니다.

헤더파일

DisjointSet.h

#ifndef DISJOINTSET_H
#define DISJOINTSET_H

#include <stdio.h>
#include <stdlib.h>

typedef struct tagDisjointSet {
	struct tagDisjointSet* Parent;
	void* Data;
} DisjointSet;

void DS_UnionSet(DisjointSet* Set1, DisjointSet* Set2);
DisjointSet* DS_FindSet(DisjointSet* Set);
DisjointSet* DS_MakeSet(void* NewData);
void DS_DestroySet(DisjointSet* Set);

#endif

DisjointSet 구조체를 보면, 부모노드의 주소값을 저장하는 멤버변수가 있습니다.

void DS_UnionSet(DisjointSet* Set1, DisjointSet* Set2); -> 집합에 추가시키는 함수
DisjointSet* DS_FindSet(DisjointSet* Set); -> 부모집합을 찾는 함수
DisjointSet* DS_MakeSet(void* NewData); -> 집합 생성 함수
void DS_DestroySet(DisjointSet* Set); -> 집합 삭제 함수

소스파일

DisjointSet.c

#include "DisjointSet.h"

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

DisjointSet* DS_MakeSet(void* NewData) {
	DisjointSet* NewNode = (DisjointSet*)malloc(sizeof(DisjointSet));
	NewNode->Data = NewData;
	NewNode->Parent = NULL;

	return NewNode;
}

void DS_DestroySet(DisjointSet* Set) {
	free(Set);
}

함수 자체도 어려운 것이 없어서, 하나씩 보겠습니다.

void DS_UnionSet(DisjointSet* Set1, DisjointSet* Set2) {
	Set2 = DS_FindSet(Set2); -> Set2의 부모노드를 찾는다.
	Set2->Parent = Set1; -> Set2의 Set1의 주소값을 부모노드 자리에 저장한다.
}

DisjointSet* DS_FindSet(DisjointSet* Set) {
	while (Set->Parent != NULL) { -> 제일 부모노드가 나올 때까지 반복
		Set = Set->Parent; 
	}

	return Set; -> 그 집합을 반환
}

집합에 합치는 방법을 보면 대충 어떤 그림이 그려지는지 알 수 있습니다. 그리고 같은 집합이라면 서로서로 무조건 연결이 되어있다는 것도 알 수 있습니다.

DisjointSet* DS_MakeSet(void* NewData) {
	DisjointSet* NewNode = (DisjointSet*)malloc(sizeof(DisjointSet)); -> 집합 동적 할당
	NewNode->Data = NewData; -> 데이터 저장
	NewNode->Parent = NULL; -> Parent 초기화

	return NewNode; -> NewNode반환
}

void DS_DestroySet(DisjointSet* Set) {
	free(Set); -> 집합 삭제
}

실행예시

DisjointSetMain.c

#include <stdio.h>
#include "DisjointSet.h"

int main() {
	int a = 1, b = 2, c = 3, d = 4;
	DisjointSet* Set1 = DS_MakeSet(&a);
	DisjointSet* Set2 = DS_MakeSet(&b);
	DisjointSet* Set3 = DS_MakeSet(&c);
	DisjointSet* Set4 = DS_MakeSet(&d);

	printf("Set1 == Set2 : %d\n", DS_FindSet(Set1) == DS_FindSet(Set2));

	DS_UnionSet(Set1, Set3);
	printf("Set1 == Set3 : %d\n", DS_FindSet(Set1) == DS_FindSet(Set3));

	DS_UnionSet(Set3, Set4);
	printf("Set3 == Set4 : %d\n", DS_FindSet(Set3) == DS_FindSet(Set4));

	return 0;
}

결과

Set1 == Set2 : 0
Set1 == Set3 : 1
Set3 == Set4 : 1