유니온 파인드(Union Find) C++ [컴공과고씨]

알고리즘 문제들을 풀다보면 각 원소들이 속해 있는 집합을 구별해야하는 문제를 볼 수 있다.

유니온 파인드에 대한 자세한 설명은 생략하고 간단히 설명하고 구현 함수들을 보여드리겠습니다.

 

기본 개념

속해있는 집합이라고 생각하시면 됩니다.

1,2,3,4,5 라는 원소가 있다고 하면 처음에는 자신의 숫자가 속해있는 그룹 번호라고 합시다.

그룹 번호-원소로 나타내면 1-1  2-2  3-3  4-4  5-5.

여기서 1번 원소와 2번 원소를 합친다는 것은 1번 원소가 속한 그룹과 2번 원소가 속한 그룹을 합치는 것입니다.

나타내면 1-1,2  3-3,  4-4, 5-5 가 되겠죠.

여기서 2번원소와 4번 원소를 합치면? -> 1-1,2,4  3-3  4-4  5-5  가 됩니다.

이렇게 해서 같은 그룹을 만들어 나가는 것을 유니온 파인드라고 합니다.

 

parent[] : 자신이 속한 그룹 번호를 저장하는 배열.

Find함수 :  자신의 그룹 번호를 반환해주는 함수.

merge함수 : 그룹을 합치는 함수.

 

코드

int find_parent(int x){
    if(parent[x] != x)
        return parent[x] = find_parent(parent[x]) 
    return x;     
}
void merge(int a, int b){
    int x = find_parent(a);
    int y = find_parent(b);
 
    if(x != y){
        if(x < y) // 그룹번호가 더 작은 쪽으로 합치기
            parent[y] = x;
        else
            parent[x] = y;
    }    
}
 

find 함수를 보시면 return find_parent(parent[x])를 해도 되지만 저렇게 하는 이유는 함수를 호출 할 때 재귀하는 횟수가 적어지기 때문입니다.

 

이유는 만약 return find_parent(parent[x]) 이러한 형태라면 

merge를 할 때 어떤 식으로 구성이 되냐면 1,2,3,4 가 있다고 하면 

merge(1,2) -> 1-1,2 

merge(3,4) -> 1-1,2    3-3,4

merge(1,3) -> 1-1,2,3     3-4

이런식으로 구성이 되게 됩니다.

find_parent(4)를 하게 되면 3를 찾고 다시 재귀해서 1로가게 됩니다.

 

하지만 parent[x] = find_parent(parent[x]) 처럼 구현하게 된다면 

merge(1,3) 후 find_paarent(4)를 하면 1-1,2,3,4 이런식으로 한번에 이어지기 때문에 나중에 부모를 찾을 때 한번에 

그룹 번호를 알게 되는 것입니다.

 

그리고 merge 함수에 if(x<y) 이 조건은 언제든 상황에 맞게 바꾸어 줄 수 있습니다.

예를 들어 난 루트 그룹 번호를 큰 쪽으로 합치고 싶으면 if(x>y) 이런식으로 말이죠.