[기본문제풀이] union_find

 

풀이 일시 : 2020-08-06

​

합집합찾기 :

대표적인 그래프알고리즘이며 서로소집합 알고리즘이라고도 한다. 여러개의 노드가 존재할 때 두개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

​

문제 :

union find로 연결여부를 판단한다.

​

풀이 :

연결되어있다면 같은 부모를 갖게끔 초기화 해준다. 소속을 같게 해준다.

 

#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 findParent(int parent[], int a, int b) { //현재집합에 속하는지확인
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b) return 1; //현재집합에 속한다.
	else return 0; //현재집합에 속하지않는다.
}

int main() {
	int parent[11];
	for (int i = 1; i <= 10; i++) {
		parent[i] = i;
	} //각자의 parent를 각자의 수로 초기화한다.
	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("1과 5는 연결되어있나요? %d\n", findParent(parent, 1, 5));
	unionParent(parent, 1, 5);
	printf("1과 5는 연결되어있나요? %d\n", findParent(parent, 1, 5));
}