[자료구조] 스택(Stack) 응용 - 미로 탐색 프로그램

#include <stdio.h>
#include <string.h>

#define MAX_STACK_SIZE 100	// 스택의 크기
#define MAZE_SIZE 6		// 6*6 미로

// 좌표(x,y)로 구성된 스택
typedef struct StackObjectRec {
	short r;	// row
	short c;	// column
}StackObject;

StackObject stack[MAX_STACK_SIZE];	// x,y 좌표로 구성된 스택 선언
int top = -1; // top 값 초기화
StackObject here = { 1,0 };		// 미로 탐색하며 이동하는 현재 위치값
StackObject entry = { 1,0 };		// 미로의 시작 위치

// 미로 - 이동 가능한 경로는 '0'으로 표시, 출구는'x'로 표시
char maze[MAZE_SIZE][MAZE_SIZE] = {
	{'1', '1', '1', '1','1','1'},
	{'e', '0', '1', '0','0','1'},
	{'1', '0', '0', '0','1','1'},
	{'1', '0', '1', '0','1','1'},
	{'1', '0', '1', '0','0','x'},
	{'1', '1', '1', '1','1','1'}
};

void initialize() {
	top = -1;	// 전역변수로 선언한 stack의 top 변수에 대하여 -1로 설정
}

int isEmpty() { return (top == -1); }
int isFull() { return (top == (MAX_STACK_SIZE - 1)); }

void push(StackObject item) {
	if (isFull()) {
		printf("stack overflow\n");
	}
	else
		stack[++top] = item;
}

StackObject pop() {
	if (isEmpty()) {
		printf("stack underflow");
	}
	else
		return stack[top--];
}

// 현재 위치의 위,아래,왼쪽,오른쪽 && 
void pushLoc(int r, int c) {
	// 6 * 6 미로 경계 밖으로 이동하려는 경우
	if (r < 0 || c < 0)
		return;

	// 벽이 아니고 동시에 지나온 길이 아니라면 스택에 push
	if (maze[r][c] != '1' && maze[r][c] != '.') {
		StackObject tmp;
		tmp.r = r;
		tmp.c = c;
		push(tmp);

	}
}

void printStack() {
	int i;
	for (i = 5;i > top;i--)
		printf("|     |\n");
	for (i = top;i >= 0;i--)
		printf("|(%01d,%01d)|\n", stack[i].r, stack[i].c);
	printf("-------\n");
}

void printMaze(char m[MAZE_SIZE][MAZE_SIZE]) {
	int r, c;
	printf("\n\n");

	for (r = 0;r < MAZE_SIZE;r++) {
		for (c = 0;c < MAZE_SIZE;c++) {
			if (c == here.c && r == here.r)
				printf("m ");
			else {
				if (m[r][c] == 0) // 지나갈 수 있는 길
					printf("0 ");
				else
					printf("%c ", m[r][c]);
			}
		}
		printf("\n");
	}
	printf("\n");
}

void main() {
	int cnt = 0;
	int r, c;
	here = entry;	// 현재 위치 = 시작 위치

	while (maze[here.r][here.c] != 'x')	// 출구가 아니면 루프 반복
	{
		printf("\n\n[ %d단계 ] \n", ++cnt);
		printMaze(maze);
		r = here.r;
		c = here.c;

		maze[r][c] = '.';		// 내가 서있던 자리, 즉 지나온 자리로 표시
		pushLoc(r - 1, c);		// 위쪽 이동 스택에 저장
		pushLoc(r + 1, c);		// 아래쪽 이동 스택에 저장
		pushLoc(r, c - 1);		// 왼쪽 이동 스택에 저장
		pushLoc(r, c + 1);		// 오른쪽 이동 스택에 저장

		printStack();

		if (isEmpty()) {
			printf("실패\n");
			return;
		}
		else
			here = pop();

		printMaze(maze);
		printStack();
	}
	printf("\n\n성공\n");
}

 

 

ㄴㅇㅁㄴㅇㅇㄹㄴㅇㄹㅇㄹㅇㅇㄹ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ㅇㄹㅇㄴㅇㄹㅇㅇ