[Algorithm] - Union-Find(Disjoint-set)

이론

여러개의 집합이 존재 할때, 두개의 집합을 선택해서 같은 그래프에 속하는지 판단하는 알고리즘이다.

간단하게 이야기 하자면, 교집합이 있다면 한개의 집합으로 보게 하겠다는 의미이다.

예를들어, A,B 집합이 다음과 같이 있다고 했을때 A = {1,2} , B = {2,3} 2라는 교집합이 있으므로 {1,2,3} 한개의 집합으로 보겠다는 것이다. 이때 집합을 병합하는 부분이 Union, 집합에 속해있는지 확인하는부분이 Find로 볼 수 있다. 두개가 함께 사용되어 Union-Find라는 이름이 붙었다.

 

Disjoint-Set이라고도 불린다. 이름만 다르고, 동일한 알고리즘으로 볼 수 있다.

 

구현

다음과 같이 노드들의 간선이 주어졌다고 예를들어 설명하겠다.

{1,2},

{2,3},

{3,4},

{1,5},

{6,7},

{7,8},

{8,9},

위에서 얘기했다시피 집합을 합쳐주는 Union부분과 부모 노드를 확인하는 Find 부분으로 나눌수 있다.

노드는 현재 1부터 9까지 9개가 존재한다. 노드의 숫자만큼의 배열을 선언하고, 자신의 인덱스로 초기화 해준다.

자신의 인덱스로 초기화해주는것에 의미는 현재 다른 노드와 연결되어있지않고, 자기 자신만을 집합의 원소로 가지고 있는 상황을 얘기하는것이다.

초기 배열의 상황은 아래와 같다. 첫번째 행은 노드의 인덱스, 두번째 행은 부모 노드의 인덱스를 의미한다.

1	2	3	4	5	6	7	8	9
1	2	3	4	5	6	7	8	9

이제 아래의 동작을 반복하면서 연결된 노드인지 확인하고 연결해주는 동작이  Union-Find이다.

 

1. 두 노드의 부모 노드가 같은지 찾는다.

1-1. 현재 노드의 인덱스와 부모 노드의 인덱스가 같은지 확인한다 ( 즉, 현재 노드가 Root 노드임을 뜻함)

1-2. 부모노드를 참조하여 Root노드를 찾을때까지 반복한다 (재귀)

2. 두 노드의 부모 노드가 같다면 같은 집합에 포함되어있다고 할 수 있다.

2-1. 같지 않다면 부모를 합칠수 있다. (어느쪽으로 합치든 일정한 형식으로)

     ex) 부모 노드가 더 작은쪽으로,  부모 노드가 더 큰쪽으로

 

부모 노드가 더 큰쪽으로 해보겠다.

 

1. {1,2}

두 노드의 부모 노드가 같은지 찾는다. (노드 1의 부모 노드 1, 노드 2의 부모 노드 2)

노드 1과 노드 2의 부모 노드가 다르고, 각자가 Root 노드임.

노드 1의 부모 노드를 2로 변경한다.

1	2	3	4	5	6	7	8	9
2	2	3	4	5	6	7	8	9

 

2. {2,3}

노드 2의 부모 노드 2와 노드 3의 부모 노드 3이 다르고, 각자가 Root 노드임

위와 같이 노드 2의 부모 노드를 3으로 변경한다.

1	2	3	4	5	6	7	8	9
2	3	3	4	5	6	7	8	9

 

3. {3,4}

3의 부모노드와 4의 부모노드가 서로 다르고, 각자가 Root 노드임

1	2	3	4	5	6	7	8	9
2	3	4	4	5	6	7	8	9

4. {1,5}

1의 부모노드가 자기 자신의 인덱스가 아니므로 재귀를 통해 실제 부모노드를 찾는다.

1->2->3->4->4 (재귀를 통해 실제 부모 노드가 4임을 찾음)

5는 현재 자신의 인덱스를 부모로 가지고 있기때문에 Root Node이다.

따라서 4의 부모노드를 5로 변경한다.

1	2	3	4	5	6	7	8	9
2	3	4	5	5	6	7	8	9

이 뒤의 과정도 동일하다.

부모를 찾고 같은 부모를 가지고 있는지..(Find)하고, 집합을 합치는(Union) 과정이 Union-Find 라고 할 수 있다. 

아래 코드를 확인하면 이해하기 더 쉬울거라고 생각한다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> unf(10); // 예제로 최대 10개의 입력을 받는다.

int parentFind(int a)
{
    if(a == unf[a]) return a; // 노드가 가지고 있는 부모노드가 자기자신이라면 리턴
    else return unf[a] = parentFind(unf[a]);
}

void parentUnion(int a, int b)
{
    a = parentFind(a);
    b = parentFind(b);
    if(a != b) unf[a] = b; //작은 노드의 부모 노드를 큰 노드로 바꿔준다.
}

int main()
{
	for(int i=0; i < 10; i++)
    {
    	unf[i] = i; //노드의 부모 노드를 자기 자신으로 설정
    }
    
	int n;
    cin >> n;
    for(int i =0; i < n; i++)
    {
    	int v1, v2;
        cin >> v1 >> v2;
        v1 = parentFind(v1);
        v2 = parentFind(v2);
        if(v1 != v2) parentUnion(v1,v2) // 찾은 부모 노드가 다르다면 합쳐준다. 
    }
}