Lab08 Disjoint Set을 이용한 Maze 만들기 코드

 

전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct _DisjointSet {
	int size_maze;
	int* ptr_arr;
}DisjointSets;

void init(DisjointSets* sets, DisjointSets* maze_print, int num);
void Union(DisjointSets* sets, int i, int j);
int Find(DisjointSets* sets, int i);
void createMaze(DisjointSets* sets, DisjointSets* maze_print, int num);
void printMaze(DisjointSets* sets, int num);
void freeMaze(DisjointSets* sets, DisjointSets* maze_print);

void printBottomWall(DisjointSets* maze_print, int start, int num); // bottom wall의 출력을 위한 함수
void printCell(DisjointSets* maze_print, int start, int num); // cell을 출력하기 위한 함수

void init(DisjointSets* sets, DisjointSets* maze_print, int num) {
	int i;

	sets->size_maze = num * num;
	sets->ptr_arr = (int*)malloc(sizeof(int) * (sets->size_maze + 1));
	for (i = 1; i <= sets->size_maze; i++)
		sets->ptr_arr[i] = i;

	maze_print->size_maze = num * num * 2;
	maze_print->ptr_arr = (int*)malloc(sizeof(int) * (maze_print->size_maze + 1));
	for (i = 1; i <= maze_print->size_maze; i++)
		maze_print->ptr_arr[i] = 1;

	/* sets는 벽 사이의 숫자를 가리키는 변수고, maze_print는 벽을 가리키는 변수다. */

	/* i의 값을 1부터 maze_print->size_maze까지 증가시켜가면서,
	i가 2의 간격으로 한 cell의 오른쪽 벽, 아래쪽 벽을 가리킨다고 하는 것이다.
	예를 들어 숫자 1의 오른쪽 벽의 i는 1·아래쪽 벽의 i는 2, 숫자 2의 오른쪽 벽의 i는 3... 이런 식으로 말이다. */

	// 미로의 시작 위치와 끝 위치는 벽이 존재하지 않는다.
	maze_print->ptr_arr[maze_print->size_maze - 1] = 0;
}

void createMaze(DisjointSets* sets, DisjointSets* maze_print, int num) {
	while(1) {
		int i = rand() % (maze_print->size_maze) + 1; // 1부터 maze_print->size_maze 까지의 정수 중 랜덤으로 한 개의 수를 생성
		while (maze_print->ptr_arr[i] == 0 || i % (num * 2) == (num * 2 - 1) || ((i / (num * 2) >= num - 1) && (i % 2 == 0)))
			i = rand() % (maze_print->size_maze) + 1;
		/* 랜덤으로 생성한 i의 자리에 이미 벽이 없거나,
		i의 위치가 미로의 맨 오른쪽 벽이어서 그 벽을 없애면 안 되거나,
		i의 위치가 미로의 맨 아래 벽이어서 그 벽을 없애면 안 될 경우에는 i값을 랜덤으로 다시 생성한다. */

		int u, v; // 고른 edge(i)와 맞닿아 있는 수를 u, v라는 변수로 선언

		/* i가 홀수라면(= | 모양의 edge라면) u는 | 기준으로 왼쪽의 수, v는 | 기준으로 오른쪽의 수이다. */
		if (i % 2 == 1) {
			u = (i / 2) + 1;
			v = u + 1;
		}
		/* i가 짝수라면 (= - 모양의 edge라면) u는 - 기준으로 위쪽의 수, v는 - 기준으로 아래쪽의 수이다. */
		else {
			u = i / 2;
			v = u + num;
		}

		int r1, r2;
		r1 = Find(sets, u); // r1 = u가 속해있는 집합의 root
		r2 = Find(sets, v); // r2 = v가 속해있는 집합의 root

		/* r1과 r2가 다르다면 (= u와 v가 서로 다른 집합에 속해 있다면), 두 집합을 합친다. 
		   이때 노드 수가 더 적은 집합을 노드 수가 더 큰 집합에 추가하도록 설정했다. */
		if (r1 != r2) {
			int r1_num = 0, r2_num = 0;
			for (int i = 1; i <= sets->size_maze; i++) {
				if (sets->ptr_arr[i] == r1)
					r1_num++;
				if (sets->ptr_arr[i] == r2)
					r2_num++;
			}

			/* 만약 r2가 속해있는 집합의 노드 수가 더 많다면, r1 집합을 r2 집합 속으로 합치기 위해 서로 바꾼다 */
			if (r1_num < r2_num) {
				int temp = r1;
				r1 = r2;
				r2 = temp;
			}

			Union(sets, r1, r2); // r2 집합을 r1 집합 속으로 합친다!
			maze_print->ptr_arr[i] = 0; // Union에 성공했으므로 i 위치의 벽은 지운다.
		}

		for (int i = 1; i <= sets->size_maze - 1; i++) {
			/* 미로의 맨 처음부터 맨 끝까지 모두 다 같은 집합에 속해 있다면,
			   미로가 성공적으로 만들어진 것이므로 미로 만드는 함수 종료 */
			if (i == sets->size_maze - 1) {
				if (sets->ptr_arr[i] == sets->ptr_arr[i + 1])
					return;
			}
			/* 하나라도 다른 집합에 속해있는 것이 있다면,
			   이 for문을 탈출하고 다시 처음으로 돌아가 미로를 만드는 과정을 반복 */
			if (sets->ptr_arr[i] != sets->ptr_arr[i + 1])
				break;
		}
	}
}

/* k = 1부터 sets->size_maze 까지 반복하며,
  k가 집합에서 가리키는 root값이 j와 같다면 k가 가리키는 값을 i로 바꾼다.
  !!이는 root값이 j인 집합을 root값이 i인 집합 속으로 넣는 것이다!! */

void Union(DisjointSets* sets, int i, int j) {
	for (int k = 1; k <= sets->size_maze; k++) {
		if (sets->ptr_arr[k] == j)
			sets->ptr_arr[k] = i;
	}
}

int Find(DisjointSets* sets, int i) {
	return sets->ptr_arr[i];
}

void printMaze(DisjointSets* maze_print, int num) {
	for (int i = 1; i <= num; i++)
		printf("+---");
	printf("+\n");
	// 미로의 맨 위 벽을 따로 그려준다. 맨 위 벽은 랜덤하게 바뀔 일이 없기 때문이다.

	for (int i = 1; i <= num * num; i = i + num) {
		printCell(maze_print, i, num);
		printBottomWall(maze_print, i, num);
	} // 미로를 한 줄별로 출력한다. 먼저 cell을 모두 출력한 다음, 그 밑의 벽을 출력한다.
}

void printBottomWall(DisjointSets* maze_print, int start, int num) {
	printf("+"); // 맨 왼쪽의 +는 고정 출력이다.
	for (int i = start; i < start + num; i++) {
		if (maze_print->ptr_arr[i * 2] == 1) // 벽이 존재한다면
			printf("---+");
		else // 벽이 존재하지 않는다면
			printf("   +");
	}
	printf("\n");
}

void printCell(DisjointSets* maze_print, int start, int num) {
	if (start == 1) // start 인자 값이 1이라면
		printf(" "); // 미로의 시작 위치에는 벽이 없어야 하므로 한 칸 띄워준다.
	else
		printf("|"); // 그렇지 않으면 그대로 벽을 출력한다.

	for (int i = start; i < start + num; i++) {
		printf("   ");
		if (maze_print->ptr_arr[i * 2 - 1] == 1) // 벽이 존재한다면
			printf("|");
		else // 벽이 존재하지 않는다면
			printf(" ");
	}
	printf("\n");
}

void freeMaze(DisjointSets* sets, DisjointSets* maze_print) {
	free(sets->ptr_arr);
	free(sets);
	free(maze_print->ptr_arr);
	free(maze_print);
}

int main(void) {
	srand((unsigned int)time(NULL));

	int num, i;

	DisjointSets* sets, *maze_print;
	scanf("%d", &num);

	sets = (DisjointSets*)malloc(sizeof(DisjointSets));
	maze_print = (DisjointSets*)malloc(sizeof(DisjointSets));

	init(sets, maze_print, num);
	createMaze(sets, maze_print, num);
	printMaze(maze_print, num);

	freeMaze(sets, maze_print);

	return 0;
}