3장 - 미로찾기(Stack 이용)

#include <stdio.h>
#define MAX_STACK_SIZE 100 
#define M 10
#define P 10
#define EXIT_ROW 10
#define EXIT_COL 10

int maze[M + 2][P + 2]; //미로
int mark[M + 2][P + 2]; //방문기록용
typedef struct {
	short int x;
	short int y;
}offsets;
offsets move[8]; //8개의 방향을 배열에 넣어놓고 쓸 것임

typedef struct {
	short int row;
	short int col;
	short int dir;
}element;
element stack[MAX_STACK_SIZE]; //지나간 경로를 저장할 스택

void path(void) {//미로를 통과한 경로를 출력
	int i, row, col, next_row, next_col, dir;
	int found = false;
	element position;

	mark[1][1] = 1; top = 0;
	stack[0].row = 1; stack[0].col = 1; stack[0].dir = 2; //N,NE,E>2동쪽방향으로 초기화
	while (top > -1 && !found) {
		//stack이 empty가 아니고 경로를 찾지 못했을 때까지 실행

		position = pop();
		row = position.row;
		col = position.col;
		dir = position.dir;
		while (dir < 8 && !found) {
			//8방향 검사
			next_row = row + move[dir].x;
			next_col = col + move[dir].y;
			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] = 1;
				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 (i = 0; i <= top; i++)
				printf("%2d %5d", stack[i].row, stack[i].col);
			printf(" %2d %5d \n", row, col);//마지막 위치는 스택에 안 들어가기 때문
			printf(" %wd %5d \n", EXIT_ROW, EXIT_COL);
		}
		else printf(" 길이없어");
	}


}

이 코드는 Stack.h가 필요하다.

offset[8]에는 N,NE,E, ... 등 8가지 방향 정보가 담겨있는데 위 코드에는 빠져있다

 

우선 이 미로찾기 프로그램은

미로의 상,하,좌,우에 1칸씩 벽이 더 있다고 가정하고 시작한다.

 

현재 좌표에서

8방향을 바라보는데,

이동 가능한 경우는 이동하고 stack에 좌표를 넣어 기록한다.

아무곳으로도 이동이 불가능한 경우에는 stack에 있던 값을 하나 꺼내어 왔던 길로 되돌아간다.