합집합 찾기(Union-Find)

Union-Find 알고리즘 : '합집합 찾기' 의미를 가진 그래프 알고리즘이다. 이것은 서로소(Disjoint-Set)이라고 도 불리는데 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

 

다음과 같이 노드들이 연결되지 않고 존재한다고 하자.

이 때 각각의 노드들은 자기 자신만을 집합의 원소로 가지고 있다고 표현할 수 있다. 즉, 모든 값이 자기 자신을 가리키는 것이다.

 

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

다음과 같이 표로 나타냈을 때, 첫 번째 행은 '노드 번호' 두 번째 행은 '부모 노드 번호'를 의미한다.

여기서 부모 노드 번호란 해당 노드가 어떤 부모 노드에 포함되어 있는지를 의미한다

 

.자 그럼 다음과 같이 1번 노드와 2번 노드가 연결되었다고 하자.

이러한 연결을 컴퓨터상에서 프로그래밍적으로 어떻게 표현할 수 있을까? 앞서 표현했던 표를 이용하게 되는데 이 내용이 바로 Union-Find라고 생각하면 된다.

 

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

2번 노드의 부모 노드 번호가 1로 바뀌었는데 이렇게 부모 노드를 합칠 땐 일반적으로 작은 값쪽으로 합치게 된다.

따라서 합쳐진 1번 노드를 합접(Union)이라고 한다.

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

2와 3번 노드도 연결된다면 다음과 같이 표로 나타낸다. 그런데 그림으로 보면 1번과 3번은 2번 노드를 통해 연결되어 있다는 것을 알 수 있지만 컴퓨터는 이것을 어떻게 파악할 수 있을까? 1번과 3번은 부모 노드 번호가 1과 2로 다르기 때문에 한번에 파악하지 못한다. 그래서 이것을 파악하기 위해 재귀 함수가 사용된다.

 

3의 부모 노드인 2번을 먼저 찾은 후 2의 부모 노드 1을 가리키고 있으므로 3의 부모는 1이다. 라는 사실을 파악하게 된다. 재귀 함수를 통해 이 사실을 파악하게 되면 합침(Union) 연산이 일어나고 표가 새롭게 구성된다.

 

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

 

1, 2, 3번 노드는 부모 노드가 모두 1이기 때문에 세개의 노드는 모두 같은 그래프에 속한다는 사실을 알 수 있게된다.  

따라서 앞서 말한 합침(Union)과 두 개의 노드의 부모 노드가 같은 집합인지 확인하는 Find 알고리즘을 합쳐 Union-Find 알고리즘이라 한다.

 

 

#include <stdio.h>
 
//부모 노드를 찾는 함수
int getParent(int parent[], int x) {
    if(parent[x] == x) return x;
    return parent[x] = getParent(parent, parent[x]);
}
 
// 두 부모 노드를 합치는 함수
int 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;
    return 0;
}
 
int main(void) {
    int parent[11];
    for(int i = 1; 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);
 
 
}