[Data Structure] 스택 - 미로찾기

알고리즘

1. 현재 위치에서 갈 수 있는 모든 위치(상하좌우) 모두 stack에 push --(1)
2. stack에서 pop 시켜서 pop 시킨 것을 현재 위치로 설정하고 (1) 계속 반복
3. -> 갈 곳 = stack에서 pop, 안 간 곳 = 그대로 stack에 존재
4. -> 이미 간 곳을 또 가면 이미 stack에 1번 저장되었기 때문에 다시 stack에 push X 

typedef struct {
	int r; // 로우(row)
	int c; // 컬럼(column)
}cur_locate; // 현재 위치를 좌표 (r, c)로 표현

typedef struct {
	int top;
	cur_locate maze[MAX_STACK_SIZE];
}stack;

char maze[MAZE_SIZE][MAZE_SIZE] = { 
	// 갈수 없는 곳 = '1', 갈 수 있는 곳 = '0', 간 곳 표시 = '#', 입구 = 'e', 출구 = 'x'
	{'1', '1', '1', '1', '1', '1'},
	{'e', '0', '0', '0', '0', '1'},
	{'1', '0', '1', '0', '1', '1'},
	{'1', '1', '1', '0', '0', 'x'},
	{'1', '1', '1', '0', '1', '1'},
	{'1', '1', '1', '1', '1', '1'}
};

void push(stack* s, cur_locate pos) { 
	if (is_full(s)) {
		fprintf(stderr, "Error : Stack is full!!");
		return;
	}
	else {
		s->top++;
		s->maze[s->top].r = pos.r;
		s->maze[s->top].c = pos.c;
	}
}

void findLoc(stack* s, int r, int c) {
	// 갈 수 있는 (r, c) 탐색해서 stack에 push,  ('1'-갈 수 없는 곳 + '#'-이미 간 곳) = 탐색 대상에서 제외
	if (r < 0 || c < 0) return;
	if (maze[r][c] != '1' && maze[r][c] != '#') {
		cur_locate tmp;
		tmp.r = r;
		tmp.c = c;
		push(s, tmp);
	}
}

while (maze[cur.r][cur.c] != 'x') {
		r = cur.r;
		c = cur.c;
		maze[r][c] = '#'; // 방문한 곳 '#'으로 표시
		maze_print(maze);
		// 갈 수 있는 위치 (상하좌우) 탐색
		findLoc(&s, r - 1, c); // 상
		findLoc(&s, r + 1, c); // 하
		findLoc(&s, r, c - 1); // 좌
		findLoc(&s, r, c + 1); // 우

		if (is_empty(&s)) {
			printf("실패!!\n");
			return;
		}
		else {
			cur = pop(&s);
			printf("(%d %d) -> ", cur.r, cur.c);
		}
	}

 

※ Example

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

#define MAZE_SIZE 6
#define MAX_STACK_SIZE 100

typedef struct {
	int r; // 로우(row)
	int c; // 컬럼(column)
}cur_locate; // 현재 위치를 좌표 (r, c)로 표현

typedef struct {
	int top;
	cur_locate maze[MAX_STACK_SIZE];
}stack;

char maze[MAZE_SIZE][MAZE_SIZE] = { 
	// 갈수 없는 곳 = '1', 갈 수 있는 곳 = '0', 간 곳 표시 = '#', 입구 = 'e', 출구 = 'x'
	{'1', '1', '1', '1', '1', '1'},
	{'e', '0', '0', '0', '0', '1'},
	{'1', '0', '1', '0', '1', '1'},
	{'1', '1', '1', '0', '0', 'x'},
	{'1', '1', '1', '0', '1', '1'},
	{'1', '1', '1', '1', '1', '1'}
};

void init_stack(stack* s) {
	s->top = -1;
}

int is_full(stack* s) {
	return s->top == MAX_STACK_SIZE - 1;
}

int is_empty(stack* s) {
	return s->top == -1;
}

void push(stack* s, cur_locate pos) { 
	if (is_full(s)) {
		fprintf(stderr, "Error : Stack is full!!");
		return;
	}
	else {
		s->top++;
		s->maze[s->top].r = pos.r;
		s->maze[s->top].c = pos.c;
	}
}

cur_locate pop(stack* s) {
	if (is_empty(s)) {
		fprintf(stderr, "Error : Stack is empty!!");
		exit(1);
	}
	else
		return s->maze[(s->top)--];
}

void findLoc(stack* s, int r, int c) {
	// 갈 수 있는 (r, c) 탐색해서 stack에 push,  ('1'-갈 수 없는 곳 + '#'-이미 간 곳) = 탐색 대상에서 제외
	if (r < 0 || c < 0) return;
	if (maze[r][c] != '1' && maze[r][c] != '#') {
		cur_locate tmp;
		tmp.r = r;
		tmp.c = c;
		push(s, tmp);
	}
}

void maze_print(char maze[MAZE_SIZE][MAZE_SIZE]) {
	printf("\n");
	for (int i = 0; i < MAZE_SIZE; i++) {
		for (int j = 0; j < MAZE_SIZE; j++) {
			printf("%c", maze[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

int main(void) {
	int r, c;
	stack s;
	init_stack(&s);

	cur_locate cur = { 1,0 }; // 시작점

	printf("Start!! ->\n");
	while (maze[cur.r][cur.c] != 'x') {
		r = cur.r;
		c = cur.c;
		maze[r][c] = '#'; // 방문한 곳 '#'으로 표시
		maze_print(maze);
		// 갈 수 있는 위치 (상하좌우) 탐색
		findLoc(&s, r - 1, c); // 상
		findLoc(&s, r + 1, c); // 하
		findLoc(&s, r, c - 1); // 좌
		findLoc(&s, r, c + 1); // 우

		if (is_empty(&s)) {
			printf("실패!!\n");
			return;
		}
		else {
			cur = pop(&s);
			printf("(%d %d) -> ", cur.r, cur.c);
		}
	}
	printf("도착!!\n");

	return 0;
}