[C/C++] 실전 알고리즘 강좌 18강. 합집합 찾기(Union-Find)

학습 내용

---

합집합 찾기(Union-Find)

Union-Find는 대표적인 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있으며 서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

 

출처 : https://jojozhuang.github.io/algorithm/algorithm-union-find/

 

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

 

만약 여러 개의 노드가 서로 자유분방하게 존재한다면 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있는 것과 같다. 이러한 경우 모든 값이 자기 자신을 가리키도록 만들어서 표현할 수 있다.

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

 

이때 1과 2가 연결되었다면 다음과 같이 2번째 인덱스의 값에 '1'이 들어가게 만든다. 이렇게 부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합친다. 바로 이것을 합침(Union)이라고 한다.

 

그렇다면 만약 2와 3도 연결되었다면 어떻게 표현할 수 있을까? 이는 아래와 같이 표현된다.

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

 

다만 이때 '1과 3이 연결되었는지는 어떻게 파악할 수 있는지'에 대한 의아함이 생긴다. 1과 3은 부모가 각각 1과 2로 다르기 때문에 '부모 노드'만 보고는 한 번에 파악할 수 없다. 따라서 재귀 함수가 사용된다.

 

3의 부모를 찾기 위해서 먼저 3이 가리키고 있는 2를 찾으면 2의 부모가 1을 가리키고 있으므로 결과적으로 3의 부모는 1이 되는 것을 파악할 수 있다. 이러한 과정은 재귀적으로 수행될 때 가장 효과적이고 직관적으로 언어를 작성할 수 있다. 따라서 결과적으로 합침 연산이 모두 수행되고 나면 다음과 같이 표가 구성된다.

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

 

노드 1과 2, 그리고 3의 부모가 모두 1이기 때문에 이 세 가지 노드는 모두 같은 그래프에 속한다고 할 수 있다. 이것이 바로 Union-Find의 동작 과정이다. Find 알고리즘은 두 개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘이다.

 

이를 코드로 나타내면 다음과 같다.

 

#include <stdio.h>

// 부모 노드를 찾는 함수
int getParent(int parent[], int x){
    if(parent[x] == x) return x;
    return parent[x] = getParent(parent, parent[x]);
}

// 두 부모 노드를 합치는 함수
void unionParent(int parent[], int a, int b){
    a = getParent(parent, a);
    b = getParent(parent, b);
    if(a < b) parent[b] = a;
    else parent[a] = b;
}

// 같은 부모를 가지는지 확인
int findParent(int parent[], int a, int b){
    a = getParent(parent, a);
    b = getParent(parent, b);
    if(a == b) return 1;
    else return 0;
}

int main()
{
    int parent[11];
    
    for(int i = 0; i <= 10; i++)
        parent[i] = i;
        
    unionParent(parent, 1, 2);
    unionParent(parent, 2, 3);
    unionParent(parent, 3, 4);
    unionParent(parent, 5, 6);
    unionParent(parent, 6, 7);
    unionParent(parent, 7, 8);
    printf("1과 5는 연결되어 있나요? %d\n", findParent(parent, 1, 5));
    unionParent(parent, 1, 5);
    printf("1과 5는 연결되어 있나요? %d\n", findParent(parent, 1, 5));
    
    return 0;
}

 

출력 결과 

1과 5는 연결되어 있나요? 0

1과 5는 연결되어 있나요? 1

 

이때 unionParent 함수로 1과 5를 연결하지 않고 1과 6이나 1과 7 혹은 1과 8을 연결하더라도 1과 5는 연결된다.