스택(Stack) 활용 예제 3

미로 찾기

char maze[MAZE_SIZE][MAZE_SIZE] = {
	{'W', 'W', 'W', 'W', 'W', 'W'},
	{'e', '0', 'W', '0', '0', 'W'},
	{'W', '0', '0', '0', 'W', 'W'},
	{'W', '0', 'W', '0', 'W', 'W'},
	{'W', '0', 'W', '0', '0', 'X'},
	{'W', 'W', 'W', 'W', 'W', 'W'}
};

e에서 시작해서 x를 찾아가는 미로이다. w는 벽이며 0으로만 다닐 수 있다. 현재위치는 .으로 표시된다. 

2024.07.22 - [Algorithm] - 스택 (stack)

스택 (stack)

위 글에서 이렇게 element만 구조체나 class 로 바꿔주면 2차원 배열을 활용하여 좌표로도 사용할 수 있다.

typedef struct {
	short r;
	short c;
}element;

---

typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
}StackType;

void init(StackType* s) {
	s->top = -1;
}
int is_full(StackType* s) {
	return (s->top == MAX_STACK_SIZE - 1);
}
int is_empty(StackType* s) {
	return (s->top == -1);
}
void push(StackType* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러");
		return;
	}
	else s->data[++(s->top)]=item;
}
element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러");
		exit(1);
	}
	else return s->data[(s->top)--];
}
element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러");
		exit(1);
	}
	else return s->data[(s->top)];
}

이 구조는 스택의 기본적인 뼈대이므로 기억해야한다. 기능적으로 push, pop empty, full, peek 함수와 1차원 배열을 활용하여 StackType을 나타내었으므로 구조체형태를 기억한다. 추후 연결리스트를 활용하여 스택을 만들기 전까지 사용가능하다.

문제로 돌아가서 추가로 필요한것은 미로를 나타내는 이차원배열,

좌표(element)를 조건(벽,현위치를 제외하여 이동가능한 좌표만 스택으로 push)에 따라 스택에 저장(push)할 수 있는 함수

미로를 출력하는 함수(이차원 배열 출력과 같다)

우선 초기화를 위한 현위치를 시작위치로 저장하고,

위 두 함수를 메인함수에서 출구 (x)를 찾을때 까지 반복할수있도록  반복문 안에 넣고 실행한다.

이때, 상하좌우의 값을 스택에 조건에 따라 넣을 수 있도록 

//상하좌우 가능한 방향 스택에 push
push_loc(&s, r - 1, c);	//상
push_loc(&s, r + 1, c);	//하
push_loc(&s, r, c - 1);	//좌
push_loc(&s, r, c + 1);	//우

방향에 따라 모두 함수를 호출한다.

그리고 이동했다면 pop을 통해 스택을 제거하여 남아있는 다음 좌표로 이동하면서 pop을 하는 과정을 반복한다.

if (is_empty(&s)) {
	printf("실패\n");
	return;
}
else
	current_point = pop(&s);

---

element current_point = { 1,0 }, entry = { 1,0 };

char maze[MAZE_SIZE][MAZE_SIZE] = {
	{'W', 'W', 'W', 'W', 'W', 'W'},
	{'e', '0', 'W', '0', '0', 'W'},
	{'W', '0', '0', '0', 'W', 'W'},
	{'W', '0', 'W', '0', 'W', 'W'},
	{'W', '0', 'W', '0', '0', 'X'},
	{'W', 'W', 'W', 'W', 'W', 'W'}
};

void push_loc(StackType* s, int r, int c) {
	if (r < 0 || c < 0) return;
	if (maze[r][c] != 'W' && maze[r][c] != '.') {	//벽이나 현재위치가 아니라면 r,c로 push
		element tmp;
		tmp.r = r;
		tmp.c = c;
		push(s, tmp);
	}
}

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

int main() {
	int r, c;
	StackType s;
	init(&s);
	current_point = entry;
	while (maze[current_point.r][current_point.c] != 'X') {
		r = current_point.r;
		c = current_point.c;
		maze[r][c] = '.';
		maze_print(maze);
		//상하좌우 가능한 방향 스택에 push
		push_loc(&s, r - 1, c);	//상
		push_loc(&s, r + 1, c);	//하
		push_loc(&s, r, c - 1);	//좌
		push_loc(&s, r, c + 1);	//우
		if (is_empty(&s)) {
			printf("실패\n");
			return;
		}
		else
			current_point = pop(&s);
	}
	printf("성공\n");
	return 0;
}

1

2

3

4

5

6

7

8