안녕하세요 기린입니다 :)
오늘은 합집합 찾기(Union-Find)에 대해 알아보도록 하겠습니다. Union-FInd는 대표적인 그래프 알고리즘입니다. 바로 '합집합 찾기'라는 의미를 가진 알고리즘인데요. 서로소 집합(Disjoint-Set) 알고리즘이라고도 부릅니다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다.
위와 같이 여러 개의 노드가 서로 자유분방하게 존재한다고 생각해봅시다. 이와 같이 모두 연결되지 않고 각자 자기 자신만을 원소로 가지고 있을 때 아래 표와 같이 표현할 수 있습니다.
| 노드번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 부모노드번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
첫 번째 행은 '노드 번호'를 의미하고 두 번째 행은 '부모 노드 번호'를 의미합니다. 즉, 자신이 어떠한 부모에 포함되어 있는지를 의미합니다.
위와 같이 1과 2가 연결되어 있다고 해봅시다. 이러한 '연결설'을 우리가 프로그래밍 언어로 표현하는 방법이 Unino-Find 합집합 찾기라고 생각하시면 이해가 쉬우실 겁니다.
자 그럼 합침(Union)을 수행해 볼 텐데요. 2번 노드가 1번 노드와 이어지면서 2번 노드의 부모 노드는 1로 변경됩니다. 이렇게 부모 노드를 합침 할 때는 일반적으로 더 작은 값으로 합칩니다. 합침 결과를 아래와 같이 표현할 수 있겠습니다.
| 노드번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 부모노드번호 | 1 | 1 | 3 | 4 | 5 | 6 | 7 | 8 |
그다음 2와 3도 연결되어 있다면 아래와 같이 표현할 수 있겠습니다.
| 노드번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 부모노드번호 | 1 | 1 | 2 | 4 | 5 | 6 | 7 | 8 |
3번째 노드의 부모가 2번으로 변경되는 걸 확인하실 수 있는데, 여기서 1과 3이 연결되어있는지 어떻게 파악하냐 가 중요한 부분인데요, 1과 3은 부모가 각각 1과 2로 다르기 때문에, '부모 노드'만 확인해서는 파악할 수 없습니다. 그러므로, 재귀 함수를 사용하여 부모를 찾게 됩니다.
3의 부모를 찾기 위해서는 먼저 3이 가리키고 있는 2를 찾습니다. 그리고 2가 가리키고 있는 부모 1을 찾고 1이 가리키고 있는 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 알고리즘은 두 개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘인 거죠.
자 이제 위와 같이 1, 2, 3, 4 노드가 연결되어있고 5, 6, 7, 8을 연결시킨 다음 1과 5번 노드가 같은 부모를 갖는지 확인해보는 소스코드를 작성해보겠습니다.
#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 compareParent(int parent[], int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if (a == b) return 1;
else 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);
unionParent(parent, 7, 8);
printf("Are 1 and 5 connected? %d\n", compareParent(parent, 1, 5));
unionParent(parent, 1, 5);
printf("Are 1 and 5 connected? %d\n", compareParent(parent, 1, 5));
}
부모 노드를 찾는 getParent 재귀 함수와 부모를 합치는 unionParent 함수 같은 부모 노드를 가지는지 확인하는 compareParent 함수를 선언하고 main에서 1, 2, 3, 4 노드를 합치고 5, 6, 7, 8 노드를 합친 후 1과 5번 노드가 같은 부모 노드를 갖는지 비교하여 출력해보고 1번과 5번 노드를 합친 후 다시 한번 1과 5번 노드가 같은 부모 노드를 갖는지 확인해봅니다.
결과는 위와 같습니다. 1과 5번이 연결되어 있지 않기 때문에 당연히 같은 노드를 갖지 않아 0을 출력하고 1번과 5번을 합친 후의 결과는 1이 출력되는 걸 확인하실 수 있습니다. 여기서 중요한 점은 꼭 1과 5번을 연결하지 않고 예를 들어 2번과 8번을 합치더라도 2번째 질문인 1과 5번 노드가 같은지에 대한 결과는 1로 나온다는 겁니다. 이유는 연결되어있기 때문이죠 :)
이러한 Union-Find 알고리즘은 다른 고급 그래프 알고리즘의 베이스가 되므로 반드시 알고 계셔야 합니다. 다음 시간에는 Union-Find를 응용한 크루스칼 알고리즘(Kruskal Algorithm)에 대해 알아보도록 하시죠
자 그럼 즐거운 코딩 하세요 :)
문의: ralla0405@gmail.com
