자료구조(17) - 유니온 파인드

#include <stdio.h>
#include <stdlib.h>

#define NODE 6

/*
자료 : 정수
기능1 Union : 두 원소를 입력받아 두 원소가 속한 집합을 합친다.(합집합 연산)
기능2 Find : 원소를 입력받아 소속 집합의 루트 노드 값을 반환한다.
*/

typedef struct Node* treePointer;

typedef struct Node {
	int value;
	treePointer parent;
}node;

void init(treePointer arr[]) {
	for (int i = 1; i <= NODE; i++) {
		arr[i] = (treePointer)malloc(sizeof(treePointer));

		arr[i]->value = i;
		// 각 트리의 루트에 값을 입력한다.

		arr[i]->parent = arr[i];
		// 자신을 가리키도록 한다.
	}
}// 초기화한다.

int _union(treePointer arr[], int a, int b) {
	if (a == b) {
		printf("%d and %d are same\n\n", a, b);
		return -1;
		// 같을 때 에러 처리
	}
	else if (a <= 0 ||  a > NODE) {
		printf("There is no %d element\n\n", a);
		return -1;
		//a가 유효하지 않은 값일 때
	}
	else if (b <= 0 || b > NODE) {
		printf("There is no %d element\n\n", b);
		return -1;
		//b가 유효하지 않은 값일 때
	}

	treePointer set_a = arr[a];
	treePointer set_b = arr[b];
	set_a->parent = set_b;
	// 한 트리 포인터를 다른 트리 포인터를 가리키도록 함

	return 0;
}

int find(treePointer arr[], int a) {
	treePointer temp = arr[a];
	while (temp->parent != temp) {
		temp = temp->parent;
	}
    // 루트노드를 찾음
	return temp->value;
}

int main(void) {
	treePointer arr[NODE + 1] = { NULL , };
    //전체 원소 수만큼 트리를 만들어야하기 때문에, 트리포인터 배열을 만든다.

	init(arr); // 초기화 //{ {1}, {2}, {3}, {4}, {5}, {6} }

	_union(arr, 1, 3); //{ {1, 3}, {2}, {4}, {5}, {6} }

	_union(arr, 3, 5); //{ {1, 3, 5}, {2}, {4}, {6} }

	_union(arr, 2, 4); //{ {1, 3, 5}, {2, 4}, {6} }

	for (int i = 1; i <= NODE; i++) {
		printf("%d is included by set %d\n\n", i, find(arr, i));
	}

}

#include <stdio.h>
#include <stdlib.h>

#define NODE 6

/*
자료 : 정수
기능1 Union : 두 원소를 입력받아 두 원소가 속한 집합을 합친다.(합집합 연산)
기능2 Find : 원소를 입력받아 소속 집합의 루트 노드 값을 반환한다.
*/

void init(int arr[]) {
	for (int i = 1; i <= NODE; i++) {
		arr[i] = i;
	}
}// 초기화한다.

int _union(int arr[], int a, int b) {
	if (a == b) {
		printf("%d and %d are same\n\n", a, b);
		return -1;
		// 같을 때 에러 처리
	}
	else if (a <= 0 ||  a > NODE) {
		printf("There is no %d element\n\n", a);
		return -1;
		//a가 유효하지 않은 값일 때
	}
	else if (b <= 0 || b > NODE) {
		printf("There is no %d element\n\n", b);
		return -1;
		//b가 유효하지 않은 값일 때
	}

	arr[a] = b;

	return 0;
}

int find(int arr[], int a) {
	if (a == arr[a]) {
		return a; // 루트 노드
	}
	return find(arr, arr[a]);// 부모 노드로 재귀함수 호출
}

int main(void) {
	int arr[NODE + 1] = { 0 , }; //전체 원소 수만큼 트리를 만들어야하기 때문에, 트리포인터 배열을 만든다.

	init(arr); // 초기화 //{ {1}, {2}, {3}, {4}, {5}, {6} }

	_union(arr, 1, 3); //{ {1, 3}, {2}, {4}, {5}, {6} }

	_union(arr, 3, 5); //{ {1, 3, 5}, {2}, {4}, {6} }

	_union(arr, 2, 4); //{ {1, 3, 5}, {2, 4}, {6} }

	for (int i = 1; i <= NODE; i++) {
		printf("%d is included by set %d\n\n", i, find(arr, i));
	}

}

for(int i = 1; i< 1000; i++){
    _union(i, i+1);
} // 1 ~ 1000까지 모두 한 집합

int find(int arr[], int a) {
	if (a == arr[a]) {
		return a; // 루트 노드
	}
	return arr[a] = find(arr, arr[a]);
    // 부모 노드로 재귀함수 호출
    // 동시에, 루트 노드 값을 자신의 모든 조상 노드들에 루트 노드값에 저장.
}

int _union(int arr[], int a, int b) {
	if (a == b) {
		printf("%d and %d are same\n\n", a, b);
		return -1;
		// 같을 때 에러 처리
	}
	else if (a <= 0 ||  a > NODE) {
		printf("There is no %d element\n\n", a);
		return -1;
		//a가 유효하지 않은 값일 때
	}
	else if (b <= 0 || b > NODE) {
		printf("There is no %d element\n\n", b);
		return -1;
		//b가 유효하지 않은 값일 때
	}

	int root_a = find(arr, a);
    int root_b = find(arr, b);
    //각각의 루트를 구함.

    arr[root_a] = root_b;
    // 루트와 루트를 곧바로 연결

	return 0;
}