랜덤 미로 생성 알고리즘

  BFS탐색 알고리즘을 공부하면서 미로를 탈출하는데 걸리는 최소비용, 거리, 최단 경로를 출력하는 문제를

여러 번 풀어보고, 또 내 지식으로 만들고자 복습하기도 했지만, 한 가지 아쉬웠던 점은 이러한 테스트 케이스로 사용할

미로가 그렇게 많지 않았다는 것이다. 그렇다고 미로를 수작업으로 만들수도 없는 일이었다.

 

  그래서 미로를 어떻게하면 생성할 수 있는지 검색해본 결과, 여러 알고리즘이 있었지만

그중 BFS 탐색과 짝을 이룬다 할 수 있는 DFS 탐색으로 미로를 생성하는 알고리즘을 직접 구현해보았다.

 

  BFS탐색이 방문여부 배열을 이용하여 계속 새로운 노드를 방문하면서 Queue에 추가하고, 다시 탐색하는 과정을

반복하는 알고리즘이라면, DFS는 재귀적으로 탐색하는 방식이라고 할 수 있겠다.

그렇다면 DFS탐색을 도대체 어떻게 적용해야 미로를 생성할 수 있을까?

 

  의사 코드는 대략적으로 이렇게 구성된다.

 

1 - 먼저 미로를 구성할 2차원 배열을 생성하고, 이 배열을 전부 벽으로 초기화한다.

 

2 - 그중에서 시작점을 하나 정해서 벽 대신 빈 공간으로 바꾸고, 시작점에 방문했음을 방문 여부 배열에 표시한다.

 

3 - 그 후에 4방향 중 무작위로 하나의 방향을 정해서 그곳으로 이동하고 벽을 빈 공간으로 교체한다.

 

4 - 그리고 그 위치를 기준으로 다시 탐색 후 방문하지 않은 공간에 방문하여 벽을 빈 공간으로 교체한다.

 

5 - 만약 더 이상 진행할 수 없다면 3의 과정으로 돌아간 후, 남은 방향 중 하나를 선택해서 다시 4의 과정을 진행한다.

 

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

void subDFS(char **maze, bool **visited, int y, int x) {
	int i,j,dx[4] = { -2,2,0,0 }, dy[4] = { 0,0,-2,2 }, wx[4] = { -1,1,0,0 }, wy[4] = { 0,0,-1,1 }, size = _msize(*maze) / sizeof(char), num = rand() % 24;
	int arr[24][4] = {
		{ 0,1,2,3 },{ 0,1,3,2 },{ 0,2,1,3 },{ 0,2,3,1 },{ 0,3,1,2 },{ 0,3,2,1 },
		{ 1,0,2,3 },{ 1,0,3,2 },{ 1,2,0,3 },{ 1,2,3,0 },{ 1,3,0,2 },{ 1,3,2,0 },
		{ 2,1,0,3 },{ 2,1,3,0 },{ 2,0,1,3 },{ 2,0,3,1 },{ 2,3,1,0 },{ 2,3,0,1 },
		{ 3,1,2,0 },{ 3,1,0,2 },{ 3,2,1,0 },{ 3,2,0,1 },{ 3,0,1,2 },{ 3,0,2,1 }
	};
	for (i = 0; i < 4; i++) {
		if (y + dy[arr[num][i]] >= 1 && y + dy[arr[num][i]] < size-1&&x + dx[arr[num][i]] >= 1 && x + dx[arr[num][i]] < size-1&&visited[y + dy[arr[num][i]]][x + dx[arr[num][i]]] == false) {
			*(*(maze + y + wy[arr[num][i]]) + x + wx[arr[num][i]]) = '.';
			*(*(maze + y + dy[arr[num][i]]) + x + dx[arr[num][i]]) = '.';
			*(*(visited + y + wy[arr[num][i]]) + x + wx[arr[num][i]]) = true;
			*(*(visited + y + dy[arr[num][i]]) + x + dx[arr[num][i]]) = true;
			subDFS(maze, visited, y + dy[arr[num][i]], x + dx[arr[num][i]]);	
		}
	}
}

void DFS(char **maze, bool **visited, int y, int x) {
	*(*(maze + y) + x) = '0';
	*(*(visited + y) + x) = true;
	subDFS(maze, visited, y, x);
}

char** setMaze(int size) {
	srand(time(NULL));
	char **p = (char**) malloc(sizeof(char*)*(size*2+3));
	bool **visited = (bool**)malloc(sizeof(bool*)*(size * 2 + 3));
	for (int i = 0; i < size * 2 + 3; i++) {
		*(p + i) = (char*)malloc(sizeof(char)*(size * 2 + 3));
		*(visited + i) = (bool*)malloc(sizeof(bool)*(size * 2 + 3));
		for (int j = 0; j < size * 2 + 3; j++) {
			*(*(p + i) + j) = '#';
			*(*(visited + i) + j) = false;
		}
	}
	DFS(p, visited, 1, 1);
	*(*(p + size * 2 + 1) + size * 2 + 1) = '1';
	return p;
}

void printMaze(char ***maze) {
	for (int i = 0; i < _msize(*maze) / sizeof(char*); i++) {
		for (int j = 0; j < _msize(*(*maze+i)) / sizeof(char); j++) {
			printf("%c", *(*(*maze + i) + j));
		}
		printf("\n");
	}
}

//미구현
int getPath(char ***maze) {
	return 0;
}

//미구현
void deleteMaze(char ***maze) {

}

int main(void) {
	char **maze = setMaze(10);
	printMaze(&maze);
}

 

  C에서는 배열을 선언할 때 크기를 동적으로 할당할 수 없으므로, 포인터를 이용해 2차원 배열을 구성하였다.

 

소스코드 출력 결과 - 1, 0은 시작점, 1은 도착점이다

 

소스코드 출력 결과 - 2, 0은 시작점, 1은 도착점이다

성공적으로 미로가 랜덤 하게 생성되는 것을 확인할 수 있다.