스택의 응용: 미로 문제

미로의 출구를 찾는 가장 기본적인 방법은 시행착오 방법으로서, 하나의 경로를 선택하여 한 번 시도해 보고 안 되면 다시 다른 경로를 시도하는 것이다. 문제는 현재의 경로가 출구로 이어지지 않을 때 다른 경로를 선택해야 한다는 것으로, 이를 위해 다른 경로들이 어딘가에 저장되어 있어야 한다. 현재 위치에서 가능한 경로 중 가장 가까운 경로를 쉽게 추출해야 하므로, 스택을 사용하는 것이 적합하다. 

 

현재 위치에서 갈 수 있는 방들의 좌표를 스택에 기억하였다가 막다른 길을 만나면 아직 가보지 않은 방들 중 가장 가까운 방으로 돌아가 새로운 경로를 찾아보는 것이다. 또, 한번 지나간 방을 다시 지나가면 안 되므로 각 방들을 지나갈 때마다 방문했다는 사실을 저장해야 한다.

 

문제 해결을 위하여 하나의 스택을 가정할 때, 현재 위치에서 이동이 가능한 칸들의 위치를 위, 아래, 왼쪽, 오른쪽의 순서로 스택에 저장하고 스택에서 맨 위의 위치를 꺼내어 현재 위치로 한 다음에 같은 작업을 반복한다. 이 반복은 현재 위치가 출구와 같거나 모든 위치를 다 검사해 볼 때까지 계속된다. 이미 검사한 위치는 표시하여 무한 루프에 빠지지 않게 한다.

 

이와 같은 알고리즘을 의사코드로 표현하면 아래와 같다.

 

위 의사코드를 바탕으로 미로 탐색 알고리즘을 C언어로 구현해보자. 2차원 배열 maze[][]를 이용하여 미로를 표현하며, 배열의 값이 0이면 갈 수 있는 길, 1이면 지나갈 수 없는 벽을 의미한다. 출구는 x로, 방문이 끝난 위치는 '.'으로, 현재 위치 m은 (행, 열)의 좌표값으로 표시한다. 따라서 스택에 저장되는 데이터는 (행, 열) 좌표가 되어야 하므로, (행, 열) 좌표를 저장할 수 있는 구조체를 만들면 된다. 반복이 끝난 후 스택이 비었는데도 출구를 찾지 못했다면 탐색이 실패했음을 출력하고 프로그램을 종료한다.

---

프로그램 4.9 미로 탐색 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
#define MAZE_SIZE 6

typedef struct {
	short r;	//행
	short c;	//열
}element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

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

element here = { 1,0 }, entry = { 1,0 };
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 push_loc(StackType* s, int r, int c) {
	if (r < 0 || c < 0) return;
	if (maze[r][c] != '1' && maze[r][c] != '.') {
		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(void) {
	int r, c;
	StackType s;

	init_stack(&s);
	here = entry;
	while (maze[here.r][here.c] != 'x') {
		r = here.r;
		c = here.c;
		maze[r][c] = '.';
		maze_print(maze);
		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
			here = pop(&s);
	}
	printf("성공\n");
	return 0;
}

>>