분리집합
2014-10-20
|
by hechl1
2445
안녕하세요.
군 전역을 하고 복학을 준비중인 컴퓨터과학과 학생입니다.
분리집합에 관하여 공부 하던 중 궁금증이 생겨 질문 올려봅니다.
집합탐색(Find) 부분인데요. 책에서 말하기를 "집학 내의 어떤 노드든 루트 노드가 나타내는 집합이 곧 자신이 속해 있는 집합이므로, 해당 원소가 어떤 집합에 속해 있는지 알려면 원소가 속해 있는 트리의 루트 노드를 찹으면 됩니다."라고 하는데요.
제가 궁금 한것은 여러개의 집합 중에서 그 원소가 속해있는 트리를 어떡해 찾는지 입니다.
예를 들어 아래와 같이 3개의 집합이 있다고 하면,
Set1 = {1,5,2,6,8}
Set2 = {22,19,57,58,69}
set3 = {120,153,145,186,155}
이 세개의 집합 중(각 집합이 어떠한 원소를 갖고 있는지 모르는 상태에서) 57이라는 원소가 어느 집합에 있는지를 찾으려면 어찌해야 하는지가 궁금합니다.
제가 잘못 이해 했을지도 모르지만 ... 책에서는 아래의 코드로 집합의 루트만 찾으면 된다고 하는데 루트를 찾는 것 만으로 어떡해 특정 원소를 찾을수 있는지가 궁금 해서요.
DisjointSet* DS_FindSet ( DisjointSet* Set )
{
while ( Set -> Parent != NULL)
Set = Set -> Parent;
return Set;
}
제가 생각 해보았던 것은 if-else로
if (DS_FindSet(Set1) == 57) 이런식인데 DS_FindSet함수는 포인터를 리턴 하고 있기에 인티저와 비교 불가능 하고,
마찬가지로 DS_FindSet(57)와 같이 함수의 아규먼트로 인티저를 넣을수도 없으니, 함수의 구현부를 바꿔야 하는것이 아닌가 생각 해보는데 .... 책에서 나온것은 위 함수만으로도 특정원소가 속한 집합을 찾을수 있다고 하니 ...
헷깔립니다....
설명 부탁드립니다!!!!!