chapter 3-1 : Stack & Queue (MAZE 미로)

스택을 이용하여 미로를 만들 수 있습니다.

maze[13][17] 미로 탐색

 

 

MAZE (미로 만들기 (stack 활용))

Initilize (미로 초기화)

먼저 2차원 배열을 통해 미로를 생성해 줄것입니다.

미로는 1과 0으로 이루어져있는데 

0은 갈 수 있는 길이고 1은 막힌 길입니다.

우리가 미로를 통과하게 경로를 탐색하는

과정에서 벗어나지 않게 

미로의 둘레를 막힌 길 1로 둘어쌓아줍니다.

따라서 2차원 배열의 행과 열을

ROW와 COL이라 할때, 실제적으로는 

ROW+2, COL+2 입니다.

결국 미로 2차원 배열은 maze[ROW+2][COL+2] 라고 선언 가능합니다. 또한 시작점과 미로의 끝 점은 

maze[1][1] 과 maze[ROW][COL] 이라고 할 수 있습니다.

 

void initialize() {//미로 초기화
	srand((unsigned)time(NULL));
	for (i = 0; i < ROW; i++) {
		for (j = 0; j < COL; j++) {
			if ((i == 1 && j == 1) || (i == ROW - 2 &&j== COL - 2))
				maze[i][j] = 0; //미로 입구와 출구를 0으로 초기화
			else if (i == 0 || j == 0 || i == ROW - 1 || j==COL - 1)
				maze[i][j] = 1; //미로 둘레를 1로 초기화
			else
				maze[i][j] = rand() % 2; //미로에 0또는 1을 랜덤으로 할당 받음
		}
	}
	/* 생성된 미로를 출력*/
	printf("\t\t-maze-\n");
	printf("   ");
	for (j = 0; j < COL; j++)
		printf(" %d", j); //COL을 출력
	printf("\n\n");
	for (i = 0; i < ROW; i++) { //ROW를 출력
		printf("%2d ", i);
		for (j = 0; j < COL; j++) {
			printf(" %d", maze[i][j]);
		}
		printf("\n");
	}
	for (i = 0; i < ROW; i++) {
		for (j = 0; j < COL; j++) {
			mark[i][j] = 0;
		}
	}
	printf("\t\t-maze-\n");

}

먼저 srand 함수를 사용하여 미로를 랜덤으로 할당 받을 준비를 합니다.

그 다음 이중 for문으로 미로의 테두리는 1로 , 시작점은 0, 끝점은 0 으로 초기화 해주고

나머지 미로들은 rand() %2 함수를 사용하여 0과 1로 랜덤으로 초기화 해줍니다.

밑의 코드들은 그냥 만든 미로를 출력해주는 코드입니다.

---

미로의 탐색 가능한 경로

미로는 상하좌우 뿐만 아니라 

대각선 방향 까지 포함하여 총 8방향으로 이동가능합니다.

미로가 그 다음 이동할 위치를 선택할때, 

8방향을 다 탐색하면서 그 방향이 0인지 1인지

확인한후 1이면 다음 위치를 탐색하고 0이면 

이동해줍니다.

 

 

 

typedef struct {
	int vert; //수직 좌표
	int horiz; //수평 좌표
}offsets;
//이동 가능 방향들의 배열
offsets move[8]= { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };

위의 구조체를 통해 이동할 부분을 탐색하면서 진행할 것입니다.

---

전역변수 설정 및 준비 작업

이제 각 함수에서 사용할 변수와 배열을 전역변수로 설정해줄 것입니다.

#define MAX_STACK_SIZE 100
#define TRUE 1
#define FALSE 0
#define ROW 13
#define COL 17
#define EXIT_ROW ROW-2
#define EXIT_COL COL-2

먼저 미로에서 이동가능한 행과 열을 저장할 Stack의 크기를 100으로 설정합니다.

TRUE와 FALSE는 나중에 경로를 탐색할때, 한번 지나왔던 경로인지 아닌지 체크하기 위해 사용합니다.

만약 경로가 TRUE면 이전에 한번 지나왔던 경로기 때문에 갈 필요가 없기 때문입니다.

ROW 와 COL은 제가 임의로 지정한 행열의 크기 입니다.

EXIT_ROW와 EXIT_COL은 미로의 마지막 통과 지점입니다. 즉, 도달했다는 의미입니다.

typedef struct {
	short int row;
	short int col;
	short int dir; //방향 표시
}element;
element stack[MAX_STACK_SIZE];
int maze[ROW][COL]; //미로변수
int mark[ROW][COL]; //지나간 길 표시 할 변수
int top; //stack의 맨위
int i,j, row, col, next_row, next_col, dir, found = FALSE;

구조체 element를 만들어 stack의 기본 요소를 저장할 배열을 선언해줍니다.

maze 배열은 미로이고, mark 배열은 미로에서 지나왔는지 안왔는지 체크해주는 배열입니다. 

변수top은 stack의 맨위를 가리키는 변수이고, i, j 는 for문 사용할때 쓸 변수입니다.

row, 와 col은 현재 위치이고, next_row, next_col은 다음 이동할 위치입니다. dir은 방향을 저장할 변수이고

found는 FALSE로 초기화 해주었는데, 만약 배열의 마지막 지점에 도달하면 TRUE로 바꾸어서 종료할 변수입니다.

---

미로 경로 찾기

void path() {
	element position;
	mark[1][1] = 1; //첫 시작점은 바로 방문하기 때문에 1
	top = 0;
	stack[0].row = 1; stack[0].col = 1; stack[0].dir = 1; //시작점 스택에 넣기

먼저 구조체 element를 사용하여 position 변수를 선언합니다.

position변수는 미로의 현재위치를 임의로 저장할 변수입니다.

mark[1][1]은 시작점이므로 이미 갔다온적이 있다는 표시 (1)를 해줍니다.

현재 스택에 현재위치가 들어올것이므로 top을 0으로 초기화해주고

stack에 현재위치(시작점)를 넣어줍니다.

while (top > -1 && !found) { //방문 안한곳
		position = pop();
		row = position.row;
		col = position.col;
		dir = position.dir;
		while (dir < 8 && !found) { //다음 위치로 이동
			next_row = row + move[dir].vert;
			next_col = col + move[dir].horiz;
			if (next_row == EXIT_ROW && next_col == EXIT_COL) //출구를 찾았을 경우
				found = TRUE;
			else if (!maze[next_row][next_col] && !mark[next_row][next_col]) { //다음 위치로 갈때
				mark[next_row][next_col] = TRUE; //방문 표시
				position.row = row;
				position.col = col;
				position.dir = ++dir; //방향 저장
				push(position);
				row = next_row; col = next_col; dir = 0;
			}
			else ++dir; //다음 위치로 갈 수 없을때
		}
	}

첫번째 while 문에서는 이제 방문안한곳을 탐색할 준비를 합니다. 현재위치를 저장할 임의의 변수 position에다가

방금전에 stack에 들어있던 정보를 pop해주어 position에 옮겨 줍니다.

따라서 변수 row, col, dir에는 현재 위치의 정보가 들어가게 됩니다.

잠시 pop 함수를 살펴보겠습니다.

element pop() {
	element result;
	if (top < 0)
		printf("stack is empty\n");
	else {
		result = stack[top];
		top--;
	}
	return result;
}

두번째 while 문에서는 본격적인 경로 탐색을 해줍니다. dir이 8이되면 더이상 갈곳이 없는 의미, 또한 found가 TRUE면

미로를 완전히 통과했다는 의미이므로 그전까지 계속 미로를 탐색하는 것입니다.

next_row, next_col에 각각 현재 위치(row, col) + move배열을 이용하여 다음위치로 초기화 해줍니다.

이제 if, else if, else 문으로 들어가는데 차례대로 

if문은 미로의 마지막 출구 즉, 완전히 통과한경우

else if문은 다음위치가 0이어서 다음위치로 이동가능할 경우

else 문은 다음위치가 1이어서 다음위치로 갈 수 없는경우 입니다.

 

먼저 if문은 다음위치가 EXIT_ROW, EXIT_COL 즉, 미로에 출구일 경우 found 변수를 TRUE로 만들어 완전히 while문을 

탈출합니다.

else if문은 다음위치에 갈 수 있다는 의미이므로 

mark[next_row][next_col]을 방문했다는 표시(1)를 해주고 position변수에 현재위치 정보를 넣어줍니다.

그 position변수를 push 함수를 이용하여 stack에 넣어줍니다.

그러고나서 현재위치(row, col)를 다음위치(next_row, next_col)로 초기화 해줍니다.

else 문은 다음위치로 갈 수 없으므로 그냥 dir의 값만 증가합니다.

if (found) {
		printf("The path is : \n");
		printf("row  col\n");
		for (int i = 0; i <= top; i++) 
			printf("%2d%5d\n", stack[i].row, stack[i].col);
		printf("%2d%5d\n", row, col);
		printf("%2d%5d\n", EXIT_ROW, EXIT_COL);
		
	}
	else printf("경로없음\n");

경로를 출력하는 부분입니다.

found가 TRUE면 미로에 탈출했다는 의미이므로 지금까지의 경로를 Stack에 저장했으므로 모든 Stack의 원소를

출력해주고 현재위치와 마지막 미로의 탈출 위치를 출력해주면 됩니다.

반대로 found가 FALSE면 못찾았다는 의미이므로 "경로 없음" 출력해주면 됩니다.

---

전체 코드입니다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define MAX_STACK_SIZE 100
#define TRUE 1
#define FALSE 0
#define ROW 13
#define COL 17
#define EXIT_ROW ROW-2
#define EXIT_COL COL-2
typedef struct {
	int vert; //수직 좌표
	int horiz; //수평 좌표
}offsets;
offsets move[8]= { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };//이동 가능 방향들의 배열
typedef struct {
	short int row;
	short int col;
	short int dir;
}element;
element stack[MAX_STACK_SIZE];
int maze[ROW][COL]; //미로변수
int mark[ROW][COL]; //지나간 길 표시 할 변수
int top;
int i,j, row, col, next_row, next_col, dir, found = FALSE;
void initialize();
void path();
element pop();
void push(element position);
int main() {
	initialize();
	path();
	return 0;
}
void path() {
	element position;
	mark[1][1] = 1; //첫 시작점은 바로 방문하기 때문에 1
	top = 0;
	stack[0].row = 1; stack[0].col = 1; stack[0].dir = 1; //시작점 스택에 넣기
	while (top > -1 && !found) { //방문 안한곳
		position = pop();
		row = position.row;
		col = position.col;
		dir = position.dir;
		while (dir < 8 && !found) { //다음 위치로 이동
			next_row = row + move[dir].vert;
			next_col = col + move[dir].horiz;
			if (next_row == EXIT_ROW && next_col == EXIT_COL) //출구를 찾았을 경우
				found = TRUE;
			else if (!maze[next_row][next_col] && !mark[next_row][next_col]) { //다음 위치로 갈때
				mark[next_row][next_col] = TRUE; //방문 표시
				position.row = row;
				position.col = col;
				position.dir = ++dir; //방향 저장
				push(position);
				row = next_row; col = next_col; dir = 0;
			}
			else ++dir; //다음 위치로 갈 수 없을때
		}
	}
	if (found) {
		printf("The path is : \n");
		printf("row  col\n");
		for (int i = 0; i <= top; i++) 
			printf("%2d%5d\n", stack[i].row, stack[i].col);
		printf("%2d%5d\n", row, col);
		printf("%2d%5d\n", EXIT_ROW, EXIT_COL);	
	}
	else printf("경로없음\n");
}
void initialize() {//미로 초기화
	srand((unsigned)time(NULL));
	for (i = 0; i < ROW; i++) {
		for (j = 0; j < COL; j++) {
			if ((i == 1 && j == 1) || (i == ROW - 2 &&j== COL - 2))
				maze[i][j] = 0; //미로 입구와 출구를 0으로 초기화
			else if (i == 0 || j == 0 || i == ROW - 1 || j==COL - 1)
				maze[i][j] = 1; //미로 둘레를 1로 초기화
			else
				maze[i][j] = rand() % 2; //미로에 0또는 1을 랜덤으로 할당 받음
		}
	}
	/* 생성된 미로를 출력*/
	printf("\t\t-maze-\n");
	printf("   ");
	for (j = 0; j < COL; j++)
		printf(" %d", j); //COL을 출력
	printf("\n\n");
	for (i = 0; i < ROW; i++) { //ROW를 출력
		printf("%2d ", i);
		for (j = 0; j < COL; j++) {
			printf(" %d", maze[i][j]);
		}
		printf("\n");
	}
	for (i = 0; i < ROW; i++) {
		for (j = 0; j < COL; j++) {
			mark[i][j] = 0;
		}
	}
	printf("\t\t-maze-\n");
}
element pop() {
	element result;
	if (top < 0)
		printf("stack is empty\n");
	else {
		result = stack[top];
		top--;
	}
	return result;
}
void push(element position) {
	top++;
	stack[top].row = position.row;
	stack[top].col = position.col;
	stack[top].dir = position.dir;
}