유니온 파인드

https://ssungkang.tistory.com/entry/Algorithm-유니온-파인드Union-Find 을 참고해서 작성한 게시글입니다.

공부용으로 작성한 글이기때문에 문제가 있으면 알려주세요!

유니온 파인드 알고리즘이란?

그래프 알고리즘의 일종. 상호 배타적 집합. Disjoint Set 이라고 합니다. 여러 노드가 존재할 때, 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘입니다. 그러기 위해서는 두 가지 연산이 존재합니다.

1. Find

   노드 x 가 어느 집합에 포함되어있는지 찾는 연산

2. Union

   노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산

유니온파인드 구현

• 구현은 간단한 트리를 통해서 이뤄집니다.

  parent[i] 를 i 노드의 부모 노드라고 정의하고 초기화해줍니다.

  parent[i]=i 인 경우, 루트 노드임을 의미합니다.

  int parent[MAX_SIZE];
  
  for(int i=0; i<MAX_SIZE;i++)
      parent[i]=i;

find 함수 구현

int find(int x){
    if(x==parent[x]){
        return x;
    }else{
        return find[parent[x]];
    }
}

x==parent[x] 라면 부모 노드가 자기 자신, 즉 본인이 루트 노드라는 의미입니다.

따라서 이 자체를 그대로 return 해줍니다. 그렇지 않다면, 재귀적으로 루트를 찾아 반환해줍니다.

이런 식으로 구현하는 경우, tree 가 치우친경우, 루트노드를 찾는데, O(n)의 시간복잡도가 발생해 tree 로 구현하는 이점이 사라집니다.

find 효율 높이기

int find(int x){
    if(x==parent[x]){
        return x;
    }else{
        int y = find(parent[x]);
        parent[x]=y;
        return y;
    }
}

루트 노드인 y를 찾으면, x의 부모를 바로 루트 노드로 바꿔줘 아래와 같이 바꿔줍니다. 결과적으로 find 의 효율을 높일 수 있습니다.

union 함수 구현

union 함수는 매개변수로 두 개의 값을 받습니다. 두 노드가 포함된 집합을 합쳐줘야합니다.

void union(int x, int y){
    x= find(x);
    y=find(y);
    if(x!=y)
    {parent[y]=x;}
}

find를 통해 각각의 root 를 찾아준 뒤, 두 집합의 root 가 다른 경우, y의 부모 노드를 x로 바꿔주도록합니다

효율적인 union 함수 구현

트리의 높이가 낮은 트리가 높은 트리의 밑으로 들어가는 것이 좀 더 효율적이기 때문에 트리의 높이를 기록해야합니다.

트리의 높이를 기억하는 rank 라는 배열을 선언하고 초기화해줍니다.

int rank[MAX_SIZE];
for(int i =0; i< MAX_SIZE; i++)
    rank[i]=1;

이제, union 할 시, 크기를 비교해주고 합쳐줄 경우, 크기를 갱신해줍니다.

void union(int x, int y ){
    x= find(x);
    y= find(y);
    if(x==y)
       return;
    if(rank[x]> rank[y]){
        parent[y]=x;
        rank[x]+=rank[y];
    }else{
        parent[x]=y;
        rank[y]+=rank[x];
    }
}

이 코드의 단점은, rank 도 저장을 해주고, parent 도 저장을 해주기 때문에 메모리를 2배나 사용한다는 단점이 있습니다.

이러한 단점을 개선하기 위해 weighted union find 알고리즘이 고안되었습니다.

Weighted Union Find

여기서는 음수의 개념이 도입이 됩니다. 부모 노드와 그룹의 사이즈를 음수와 양수로 구분해 표기하는 방법입니다.

위의 그림처럼, parent 의 배열이 음수일경우, 루트 노드로 해당 집합에 속한 노드의 사이즈를 표기하고, 양수일 경우, 자식노드로 부모노드를 가르키게 됩니다.

int parent[MAX_SIZE];
for(int i=0; i< MAX_SIZE; i++)
        parent[i]=-1;

int find(int x){
    if(parent[x]<0)
            return x;
}else{
    int y = find(parent[x]);
    parent[x]=y;
    return y;
    }
}


void union(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)
        return;
    // parent 값이 더 작은 것이 높이가 더 높다.
   if(parent[x]<parent[y])
   {
       parent[x]+=parent[y];
       parent[y]=x;

   }else{
       parent[y]+=parent[x];
       parent[x]=y;
   }
}

참고 문헌

https://ssungkang.tistory.com/entry/Algorithm-유니온-파인드Union-Find