합집합 찾기(Union-Find) 알고리즘

합집합 찾기(Union-Find)

Union-Find는 대표적인 그래프 알고리즘이며 서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다.
여러 개의 노드가 존재할 때 두 개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.
Union-Find는 두 가지 연산으로 이루어져 있다.
- Find() : x가 어떤 집합에 포함디어 있는지 찾는 연산
- Union() : x와 y가 포함되어 있는 집합을 합치는 연산

다음의 그림을 보자

위와 같이 여러 개의 노드가 서로 자유분방하게 존재한다고 생각해보자. 이와 같이 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때를 다음과 같이 표현할 수 있다. 모든 값이 자기 자신을 가리키도록 만드는 것이다. 아래 표에서 첫 행은 노드 번호를 의미하고 두 번째 행은 부모 노드 번호를 의미한다. 즉, 자신이 어떠한 부모 노드에 포함되어 있는지를 의미한다.

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	2	3	4	5	6	7	8

이 때 위와 같이 1과 2가 연결되었다고 해보자. 이러한 연결성을 프로그래밍 언어로 어떻게 표현할 수 있을 지에 대한 내용이 Union-Find라고 생각하면 된다.

노드 번호	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이 되는 것이다. 이러한 과정은 재귀적으로 수행될 때 효과적으로 표현할 수 있다. 그래서 결과적으로 합침(Union)연산이 모두 수행되고 나면 다음과 같이 표가 구성된다.

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	1	1	4	5	6	7	8

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

#include<iostream>

using namespace std;

// 부모 노드를 찾는 함수
int getParent(int parent[], int x)
{
	if (parent[x] == x)	return x; // 부모 노드가 자신인 경우 리턴
	else return parent[x] = getParent(parent, parent[x]);
	// 부모 노드의 값과 자신이 다르다면 재귀 호출
}

// 두 부모 노드를 합치는 함수
void unionParent(int parent[], int a, int b)
{
	a = getParent(parent, a); // a의 부모 노드 확인
	b = getParent(parent, b); // b의 부모 노드 확인
	if (a < b) parent[b] = a; // 더 작은 값을 부모 노드로 지정
	else parent[a] = b;
}

// 같은 부모를 가지는지 확인
int findParent(int parent[], int a, int b)
{
	a = getParent(parent, a); // a의 부모 노드 확인
	b = getParent(parent, b); // b의 부모 노드 확인
	if (a == b) return 1; // 같은 부모를 가진다면 1을 리턴
	else return 0; // 다르다면 0리턴
}

int main(void)
{
	int a, b; // 연결을 확인할 두 노드 번호
	int parent[11]; // 각 노드의 부모를 담을 배열 (인덱스 : 자식 노드, 값 : 부모 노드)
	for (int i = 1; i < 11; i++)
		parent[i] = i;
	unionParent(parent, 1, 2);
	unionParent(parent, 2, 3);

	cout << "연결되어 있는지 확인할 노드 번호 : ";
	cin >> a >> b;
	cout << a << "와 " << b << "의 연결 여부 : " << findParent(parent, a, b) << endl;

}

위와 같은 상태에서는 1과 3이 연결되어 있는 것을 볼 수 있으며 unionParent()함수를 사용하여 다른 노드의 부모 노드를 연결하면 연결한 노드의 연결 여부가 정상적으로 출력되는 것을 확인할 수 있을 것이다.

참조
https://blog.naver.com/ndb796/221230967614
https://brenden.tistory.com/33?category=747314

Algorithm

합집합 찾기(Union-Find)

FEATURED TAGS

FRIENDS