Union-Find(Disjoint-Set) 합집합 찾기

Kruskal 알고리즘 전제 지식으로 배웠다.

Kruskal 알고리즘이 정확히 기억 안 나서 책을 다시 봤다.

Kruskal - MST(Minimmum Spanning Tree; 최소비용 신장 트리)의 일종으로써 Greedy Method를 이용한다.

MST의 원리에 따라 1. 각단계 사이클을 이루지 않는(T!) 최소 비용 간선을 선택하며, 2. 모든 정점을 최소 비용으로 연결하는 최적 해답을 구한다.

또한 Greedy Method의 원리에 따라 최적의 해를 구한다.

 

Union-Find는 연결성을 표현하는 연산의 일종으로, 꼭 Kruskal 알고리즘에서만 사용되는 것은 아니다.

(중요하다ㅏ)

 

---

 

정의

Union-Find(Disjoint-Set) - 두 노드를 선택하고 같은 그래프에 속하게 하거나, 같은 그래프(집합)에 속하는지 판별한다. (조상이 같은지 판단)

 

과정

크게 Union과 Find 두 가지로 구분할 수 있다.

*전제

0. 자기 자신만을 원소로 갖고 있다. (임의 설정)

*Union

1. 부모를 합친다.

*Find

2. 부모를 확인해 같은 집합에 속하는지 확인한다.

 

구체적 설명 / 구현

0. 자기 자신만을 원소로 갖고 있다. (임의 설정)

맨 처음 각 노드들은 자기 자신만을 원소로 갖게 한다. (설정하기 나름)

int parent[11]; //전역변수
//main
for(int i = 1; i <= 10; i++) { //인덱스 주의-1~10을 사용
	parent[i] = i;
}

*parent - 각 노드들의 최상의 부모임을 의미 / 인덱스: 번호, 값 : 최상위 부모

 

(Union)

1. 부모를 합친다. 

두 노드를 비교했을 때, 더 작은 노드를 부모로 삼는다. 마찬가지로 설정하기 나름이다. (일반적이라고 한다.)

//main에서 함수 호출
unionParent(1, 2);

//union parent
void unionParent(int a, int b) {
	a = getParent(a);
  	  b = getParent(b);
    	if(a<b) 
    		parent[b] = a; //더 작은 노드가 부모가 됨
    	else 
    		parent[a] = b;
}

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

 

+ 재귀함수를 사용하는 이유

본론부터 이야기하면 부모의 부모, 즉 같은 조상을 가리키도록 해야 하는데, 이를 위해 getParent 재귀 함수가 사용된다.

재귀 함수를 사용하지 않으면 1과 2의 부모는 1인데, 2와 3의 부모는 각각 1, 2가 되어버릴 수도 있다.

재귀 함수를 사용하면 같은 조상을 갖게 만들 수 있는데, 그냥 순서를 쭉 표현해본다.

---

main----

unionparent(2, 3);

 

unionparent----

a(->2) = getParent(2);

b(->3) = getParent(3);

 

1. getParent(a의 경우)----

(if문)parent[2] != 2   :if문 만족 안 함, if 나감

(return문)parent[2] = getParent(1);

 

getParent(재귀호출)----

(if문)parent[1]==1   :만족 - return 1;

 

getParent(a의 경우로 돌아옴)----

(return문)parent[2] = 1;

 

unionparent(돌아옴)----

a=1;

 

2. getParent(b의 경우)----

(if문)parent[3] == 3   :if문 만족

return 3;

 

unionParent----

//a는 1, b는 3인 상태

if(1<3) parent[3] = 1;   //if문 만족, 사전 설정한 규칙에 따라 부모 설정

 

그 다음으로 3, 4를 union 한다고 생각하면, 3은 위의 2와 같은 과정을 거쳐서,

(호출과 재귀) parent[3] -> parent[2] -> parent[1] -> (return) 1 -> 1 -> 1

3의 조상은 1이 되고 4의 조상도 1이 된다.

---

(Find)

2. 부모를 확인해 같은 집합에 속하는지 확인한다.

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

 

전체적으로 소스를 합쳐본다.

#include <cstdio>

void unionParent(int a, int b);
int getParent(int x);
int findParent(int a, int b);
int parent[11];

int main() {
	for (int i = 1; i <= 10; i++) {
		parent[i] = i;	//인덱스 주의! 1~10 사용
	}
	unionParent(1, 2); //조상 1
	unionParent(2, 3);
	unionParent(3, 4);
	unionParent(5, 6); //조상 5
	unionParent(6, 7);
	unionParent(7, 8);
	printf("1과 5가 연결되어 있는지 %d \n", findParent(1, 5)); //0
	unionParent(1, 5);
	printf("1과 5가 연결되어 있는지 %d ", findParent(1, 5)); //1

	return 0;
}

void unionParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a < b)
		parent[b] = a;
	else
		parent[a] = b;
}

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

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

 

union 쓰면서 약간 노가다였지만 재밌었다.

 

 

지식 제공자 - 심오한 블록체인의 모르는 사람

 

참고 : https://blog.naver.com/ndb796/221230967614

C언어로 쉽게 풀어쓴 자료구조/천인국/생능출판