스택 응용 : 미로문제(Maze problem)

=> 깊이우선탐색(DFS) 이용

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

#define STACK_MAX_SIZE 100
#define MAZE_SIZE 6

//출발 위치:e, 벽:1, 이동 가능한 곳:0, 출구:x, 방문한 곳:.

typedef struct _RAT_POS_ {
	char row;
	char col;
}RAT_POS;

int top = -1;

void push(RAT_POS* st, RAT_POS item) {
	if (top == STACK_MAX_SIZE) {
		fprintf(stderr, "더이상 스택에 삽입할 수 없습니다\n");
		return;
	}
	else {
		top++;
		st[top] = item;
	}
}

int IsEmpty() {
	return top == -1;
}


RAT_POS pop(RAT_POS* st) {
	if (IsEmpty()) {
		fprintf(stderr, "공백스택이므로 pop할 수 없습니다\n");
		return;
	}
	else {
		RAT_POS data = st[top];
		top--;
		return data;
	}
}

void PrintMaze(char(*maze)[MAZE_SIZE], RAT_POS now) {
	//이때 현재 위치는 m으로 표시 
	printf("\n");
	for (int i = 0; i < MAZE_SIZE; i++) {
		for (int j = 0; j < MAZE_SIZE; j++) {
			if (maze[i][j] == '1' || maze[i][j] == '0') {
				printf("%d ", maze[i][j] - '0');
			}
			else if(i== now.row && j == now.col){
				printf("m ");
			}
			else {
				printf("%c ", maze[i][j]);

			}
		}
		printf("\n");
	}
}

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

void visit(char(*maze)[MAZE_SIZE], int row, int col, RAT_POS * stack) {
	
	if (row < 0 || col < 0 || row >= MAZE_SIZE || col >= MAZE_SIZE) {
		return;
	}
	else if (maze[row][col] == '.' || maze[row][col] == '1') {
		return;
	}
	else if(maze[row][col]=='0' || maze[row][col]=='x') {
		//아직 방문할 수 있는 위치이면 스택에 push한다. 
		
		
		RAT_POS now = { row,col };
		push(stack, now);
		PrintMaze(maze, now);
		printStack(stack);
	}
}

void findRoot(char (*maze)[MAZE_SIZE]) {
	RAT_POS now = { 1,0 };
	RAT_POS stack[STACK_MAX_SIZE];
	PrintMaze(maze, now);

	//상하좌우
	//(r-1,c) (r+1,c) (r,c-1) (r,c+1)

	int row = now.row;
	int col = now.col;
	while (maze[row][col] != 'x') {
		if (maze[row][col] == '0') {
			maze[row][col] = '.';
		}
		else if (maze[row][col] == '.') {
			continue;
		}
		
		
		visit(maze, row - 1, col, stack);
		visit(maze, row + 1, col,stack);
		visit(maze, row, col - 1, stack);
		visit(maze, row, col + 1, stack);

		if (IsEmpty(stack)) {
			printf("실패\n");
			return;
		}
		else {
			RAT_POS pop_pos = pop(stack);
			row = pop_pos.row;
			col = pop_pos.col;
			
		}
		
	
	}
	printStack(stack);
	printf("성공\n");
	
}


int main() {
	

	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'}
	};

	findRoot(maze);








	getchar();
	return 0;
}