DisjointSet-unionFind

Disjoint Set

번역하면 서로소 집합으로 서로 중복 되지 않는 부분 집합들로 이루어진 집합(set).

한마디로 교집합이 존재 하지 않는 부분집합들로 이루어진 집합.

Union-Find

Union : 두개의 집합을 하나의 집합으로 합치는 것.

Find : 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환하는(찾는) 것.

집합들을 tree구조로 나타내어 해당원소가 어떤 집합에 속하는지 판단할때 각 집합의 대표값(root)을 이용해서 집합이 같은지를 비교.

구현 방법

• 연결리스트

typedef struct node{
    int data;
    struct node* parent;
    struct node* next;
}node;

void MakeSet(node* p,int x){
     p->data = x;
     p->parent = p;//처음은 다 원소가 하나씩있는 집합이므로 자기 자신이 root
     p->next=null;
}

void Find(node* p,int x){
    if(p->parent->data == x) return x;  //root값이 자기 자신이라면 집합의 대표값
    else return Find(p->parent,x);  //재귀적으로 집합 대표값 찾기
}

void Union(node* p1,node* p2,int x,int y){
    x = Find(p1,x);
    y = Find(p2,y);
    p1->next = p2;
    p2->parent = p1;
}

• Disjoint Set Forest ( Tree )

int root[n];

void MakeSet(int x){
     root[x] = x;    //처음은 다 원소가 하나씩있는 집합이므로 자기 자신이 root
}

void Find(int x){
    if(root[x] == x) return x;  //root값이 자기 자신이라면 집합의 대표값
    else return Find(root[x]);  //재귀적으로 집합 대표값 찾기
}

void Union(int x,int y){
    x = Find(x);
    y = Find(y);
    root[y] = x;
}

시간 복잡도

연결리스트로 구현시 O(nlgn)의 시간을 갖으며 Tree로 구현해도 불균형한 트리 (예 : skewd tree)와 같게 되면 연결리스트와 다를 것이 없어진다.

문제점

find시에 재귀적으로 찾기 때문에 만약에 set의 tree구조가 선형적인 형태라고 한다면 최악의 경우로 O(n)만큼의 시간이 소요 되게 된다.

➡ path compression (경로 압축)기법 사용

또한, union시에 깊이가 작은 트리에 깊이가 깊은 트리를 붙이게 되면 깊이가 더 증가하여 시간에 악영향을 준다.

➡ union by rank 기법 사용

path compression (경로 압축)

find 연산 수행시마다 트리의 구조를 평평하게 만드는 방법.

각 root값을 재귀적으로 가리키는 것이 아닌 해당 집합의 속하는 원소는 모두 동일한 root를 가리키게 만드는 방법

void Find(int x){
    /*find수행마다 해당 parent값을 root로 초기화*/
    if(root[x] != x) root[x] = Find(root[x]);
    else return root[x];
}

union by rank

항상 깊이가 깊은 트리에 작은 트리를 붙여 깊이를 유지하는 방법.

깊이가 서로 같은 트리라면, 깊이를 1증가 시킨다.

int root[n];
int rank[n];

void MakeSet(int x){
    root[x] = x;    //처음은 다 원소가 하나씩있는 집합이므로 자기 자신이 root
    rank[x] = 0;    //깊이도 0으로 초기화
}

void Union(int x,int y){
    x = Find(x);    //입력받은 x값의 root값을 저장
    y = Find(y);    //입력받은 y값의 root값을 저장

    if(x==y)  return; //root가 같다면 같은 집합

    if(rank[x] < rank[y])  root[x] = y; //x의 root를 y로 변경
    else if(rank[x] > rank[y]) root[y]= x; //y의 root를 x로 변경
    else{
        root[y] = x;
        rank[x]++;  //깊이가 같다면 x에 y를 붙였으므로 x깊이 증가
    }

두 기법을 적용 후 시간 복잡도

O(lgn)

활용

Disjoint Set 자료구조는 집합의 분할을 모델링 하기 때문에 무방향 그래프(undirected graph) 의 연결된 요소들을 추적 할 수 있어, 사이클이 발생하는지 / 같은 요소에 속하는지 확인 할 수 있다.

대표적으로 MST를 찾는 Kruskal 알고리즘에 이용된다.