[C++] 합집합 찾기(Union-Find)

합집합 찾기는 그래프의 연결 유무를 판별할 때 쓰이는 알고리즘이다. 세 가지 함수만 구현하면 된다.

​

1. getParent - 부모 값 반환
2. unionParent - 부모 노드 합치기
3. findParent - 같은 부모 노드를 가지는지 확인(연결여부 판별)

​

먼저 노드 사이의 관계를 파악하기 위해 Parent라는 배열을 만든다. 노드의 개수만큼 크기 설정을 해주면 된다. 예를 들어 노드의 개수가 다섯 개면 아래와 같이 초기화해준다.

노드 사이의 연결관계는 Parent의 원소값으로 판단한다. 일반적으로 parent는 원소값이 작은 값을 기준으로 한다. 만약 1과 5를 연결하면 아래와 같다.

이제 Parent[5] = 1로 바뀐 과정을 살펴보자. 가장 기초가 되는 getParent 코드는 아래와 같다.

 

int getParent(int parent[], int x) {
	if (parent[x] == x) return x;
	return parent[x] = getParent(parent, parent[x]);
}

 

말 그대로 i번째 노드의 parent 값을 반환해주는 함수인데, parent[x] == x 가 아닌 경우 재귀함수를 통해 부모를 찾아주는 것에 유의하자. 부모가 같다는 것은 서로 연결되어있다는 것을 의미하고, 부모가 다르면 연결되어 있지 않기 때문에 열결하려면 unionParent 함수를 사용해야 한다. getParent로 부모값 일치 여부를 판단하는 findParent 함수는 아래와 같다.

 

int findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b) return 1;
	return 0;
}

 

연결되어 있지 않은 두 노드를 연결하고 싶으면 아래의 unionParent 함수를 사용하면 된다.

 

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;
}

 

Parent[5] = 1로 된 이유는 getParent로 살펴본 결과 부모값이 달라서 unionParent를 해줬는데, 부모값은 작은 값을 기준으로 하기 때문이다.

​

정리하자면.. 두 노드가 연결되었는지 확인하고 싶으면 findParent를, 연결하고 싶으면 unionParent를 사용하면 된다. getParent는 앞의 두 함수를 구현하기 위한 매개함수라고 할 수 있다.