유니온 파인드 알고리즘 활용
Disjoint Set이란 서로 중복되지 않는 부분집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조
•
Find 연산을 통해 루트 노드를 찾아가며 두 집합이 서로 같은 집합인가? 아닌가를 판단할 수 있음
•
Union 연산을 통해 여러 집합을 하나로 묶을 수 있음
•
분리집합 또는 상호 배타적 집합
•
집합이란 원소의 모임
분리 집합 (Disjoint Set) 이란 서로 공통된 원소를 갖지 않는 집합들을 말한다.
분리 집합은 두개 이상의 집합을 일컬을 때만 사용할 수 있는 개념.
A = {1, 2, 3}
B = {4, 5, 6} 일때,
두 집합 A와 B는 서로 분리 집합이다.
A = {1, 2, 3, 7}
B = {4, 5, 6, 7} 일때,
두 집합 A와 B는 서로 분리집합이 아니다.
Python
즉 분리 집합에는 교집합 (Intersection)이 있을 수 없다.
오직 합집합 (Union) 만 있을 뿐이다.
분리 집합은 집합들 간의 교집합을 허락하지 않기 때문에 서로 구분되어야 하는 데이터 집합을 다룰 때 아주 유용하다.
분리 집합의 활용
책의 가격 정보를 저장하는 자료구조가 다음과 같이 정의되어 있다고 할 때
typedef struct tagBookPrice
{
unsigned long ISBN;
unsigned long Price;
} BookPrice;
C
•
ISBN 은 책을 구분하는 전세계에서 유일한 고유 식별 번호
•
Price 는 가격을 나타낸다.
어느 날 서점의 홍보를 위해 베스트 셀러에 한해서 한시적으로 할인 판매 행사를 한다고 가정하면
할인 행사는 임시적이기 때문에 가격이 변해야 하지만, BookPrice 구조체의 Price 값을 변경해선 안된다.
또한 구조체에 베스트 셀러임을 나타내는 필드를 새로 추가하는 것은 프로그램의 로직 변경이 일어나기에 필드를 새로이 추가할 수 없다.
이때 BookPrice 구조체나 구조체의 필드, 값을 변경하지 않고 “일반 도서 집합"과 “베스트 셀러 도서 집합"을 만들고 베스트 셀러 도서들의 BookPrice 가 베스트 셀러 집합의 원소가 되게 하는 것이다.
따라서 어떤 도서의 BookPrice 객체가 베스트 셀러 집합에 속해 있는지 여부만 판단하게 되면 할인 가격으로 그 도서를 판매할 수 있고, 행사가 끝나면 베스트 셀러 집합에 속한 원소들을 다시 일반 도서 집합으로 옮기기만 하면 된다.
이처럼 분리집합은 원소 또는 개체가 “어느 집합에 소속되어 있는가?” 라는 정보를 바탕으로 하는 알고리즘에 응용할 수 있다.
한편 어떤 한 우너소가 소속되어 있는 집합을 알아내는 것을 집합 탐색 이라고 한다.
분리 집합의 표현
보통의 트리구조는 부모가 자식을 가리키는 포인터를 가지고 있으나 분리 집합에서는 자식이 부모를 가리킨다.
•
루트 노드는 집합 그 자체를 의미한다.
•
루트 노드 자신을 포함한 트리 내의 모든 노드들은 그 집합에 소속된다.
typedef struct tagDisjointSet
{
struct tagDisjointSet* Parent;
void* Data;
} DisjointSet;
C
분리 집합의 연산
합집합 연산 (Union)
•
분리 집합을 이루고 있는 트리 내의 모든 노드들은 루트 노드가 나타내는 집합 안에 있다.
•
따라서 합치고자 하는 트리의 루트 노드를 합칠 루트 노드의 자식 노드로 만들면 된다.
void DS_UnionSet(DisjointSet* Set1, DisjointSet* Set2)
{
Set2 = DS_FindSet(Set2);
Set2->Parent = Set1
}
C
집합 탐색 연산 (Find)
•
집합 탐색 연산은 집합에서 원소를 찾는 것이 아닌, 원소가 속해 있는 집합을 찾는 것
•
집합 내의 어떤 노드는 루트 노드가 나타내는 집합이 곧 자신이 속해 있는 집합이므로 해당 노드(원소)가 어떤 집합에 속해 있는지 알려면 이 원소가 속해 있는 트리의 루트 노드를 찾으면 된다.
•
분리 집합의 각 노드는 부모 노드를 가리키는 포인터가 있으므로 포인터를 따라 올라가다 부모가 NULL 인 루트 노드를 만나면 된다.
DisjointSet* DS_FindSet(DisjointSet* Set)
{
while (Set->Parent != NULL)
{
Set = Set->Parent;
}
return Set;
}
C
