Union-Find(유니온 파인드)에 대해 알아보고 구현하기

Union-Find?

 

 유니온 파인드. 그대로 해석하면 union은 조합, find는 찾다로 해석이 가능하다. 실제로 이 알고리즘은 두 연산 find와 union를 사용한다. 여러 개의 노드가 있다고 가정했을 때 2개의 노드를 union을 통해 합치는 것도 가능하고, find를 통해 해당 노드의 부모노드를 찾는 것 또한 가능하다. 

 

전체적인 구현 방법

 

노드들의 부모를 나타낼 배열을 선언해줘야한다. 예를 들어 트리를 다룬다고 했을 때 직접적으로 간선을 옮겨주는 식으로 할 수 없는가? 라는 생각을 가질 수 있으나, 가능은 하나 노드들의 부모가 하나로 통일됬는 지 검사하는 등의 연산이 필요할 경우, 시간복잡도가 난해해지므로 O(n)으로 끝낼 수 있게 노드들의 부모를 나타낼 배열을 선언해줘야한다.

부모노드가 없을 경우 자기 자신을 가르키도록 해야한다.

노드	[0]	[1]	[2]	[3]
부모 노드	0	1	2	3

(0번 노드의 부모는 0번, 1번 노드의 부모는 1번인 상태... 즉 부모노드가 없이 자기자신을 가르키고 있다.)

 

---

 

그리고 Find 함수를 만들어줘야한다.

 

Find함수는 내가 원하는 노드의 부모노드를 찾는 함수이다. 정확히는 원하는 노드의 루트노드를 찾는다. 즉 위에서 만든 노드들의 부모를 나타내는 배열인 parents 배열에서 부모노드를 찾으면 된다.

 

int find(int target){
    if(target == parents[target]) return target;
    else return find(parents[target]);
}

이런식으로 target과 parents[target]이 같으면 target을 리턴하고, 틀리면 parents[target]을 find함수의 인수로 넣어 값을 가져온다.

 

---

 

Union 함수는 매개변수를 2개를 받는다. 즉 내가 원하는 2개의 노드의 부모를 찾은 뒤 같다면 넘기고, 2개의 노드의 부모가 서로 다르다면 번호가 빠른 노드의 자식으로 나머지 노드를 달아준다.

int Union(int a, int b){
    a = find(a);
    b = find(b);
    if(a!=b){
        if(a<b) parents[b] = a;
        else parents[a] = b;
    }
}

 

Union-find의 장점

 

만약 여러 개의 노드 무리들이 있다고 가정했을 때, 2개의 노드를 선택했을 때 그 노드들이 연결이 되어있는지 찾기가 용이하다.

 

위에 그림처럼 노드들이 있다고 가정했을 때, find를 통해 3번 노드와 5번 노드가 같은 트리인지 쉽게 찾을 수 있고, union을 통해 3번과 5번을 연결하는 것도 가능하다.

노드	[0]	[1]	[2]	[3]	[4]	[5]	[6]
부모노드	0	0	0	2	4	4	4

 

또한 O(n)이라는 효율적인 시간복잡도를 가지고 있다.

 

2번 노드와 3번 노드가 연결되어있는 지 확인하는 코드

#include<iostream>

using namespace std;

int parents[4] = {0,1,2,3};

int find(int target){
    if(target == parents[target]) return target;
    else return find(parents[target]);
}

int Union(int a, int b){
    a = find(a);
    b = find(b);
    if(a!=b){
        if(a<b) parents[b] = a;
        else parents[a] = b;
    }
}

int main(){
    cout << "node 2, node 3 are connect? : ";
    if(find(2) == find(3)){
        cout << "Yes." << endl;
    }else{
        cout << "NO." << endl;
    }
    Union(2,3);
    cout << "node 2, node 3 are connect? : ";
    if(find(2) == find(3)){
        cout << "Yes." << endl;
    }else{
        cout << "NO." << endl;
    }
}

 

연습하기 좋은 문제

 

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

 

유니온 파인드 알고리즘이 개념이 좀 직관적이기 때문에, 나름 이해하는 것 자체는 쉬운데 문제의 랭크들이 좀 높게 되어있다.

 

끝맺는 말

 

알고리즘이 직관적이라 재밌고, 효율적인 알고리즘이니 확실히 익혀두도록 하자.