3. 스택의 응용

괄호 검사 문제

 

 

---

수식의 계산

 

 

---

미로 문제 ft. C언어

미로 문제(maze solving problem)

• 미로에 갇힌 생쥐가 출구를 찾는 문제이다
• 미로가 서로 연결된 여러 개의 작은 방 또는 칸으로 구성되어 있다고 가정하자

 

 

생쥐가 출구를 찾는 기본적인 방법

: 시행착오 방법으로 하나의 경로를 선택하여 한번 시도해보고 안되면 다시 다른 경로를 시도하는 것이다.

 

• 문제는 현재의 경로가 안 될 경우에 다른 경로를 선택해야 한다는 것으로 다른 경로들이 어딘가에 저장되어 있어야 한다.
• 그러면 현재 위치에서 가능한 경로 중에서 가장 가까운 경로이면 좋을 것이다
• 따라서 가능한 경로들이 저장되는데 그중에서 가장 최근에 저장한 경로가 쉽게 추출되는 자료구조인 스택이 가장 적합하다
• 구체적으로 현재 위치에서 갈 수 있는 방들의 좌표를 스택에 기억하였다가 막다른 길을 만나면 아직 가보지 않은 방 중에서 가장 가까운 방으로 다시 돌아가서 새로운 경로를 찾아보는 것이다
• 따라서 생쥐가 각 방들을 지나갈 때마다 방문했다고 표시를 하여야 한다.
• 모든 위치는 (행 [가로 값들], 열 [세로 값들])로 표시하기로 한다
• 생쥐는 현재 위치에서 위쪽과 아래쪽, 왼쪽과 오른쪽을 살펴본다
• 만약 이들 위치가 아직 방문되지 않았고 갈 수 있는 위치이면 그 위치들을 스택에 삽입한다
• 현재의 위치인 (1,0)에서 갈 수 있는 위치는 오른쪽 방향인 (1,1)뿐이다.
• 따라서 (1,1)은 아직 방문하지 않은 위치이므로 스택에 삽입된다
• 여기서 (1,0)으로 갈 수 있지만 (1,0)은 이미 방문한 것으로 표시되어 있기 때문에 스택에 삽입 x

 

 

• 2차원 문자 배열를 이용하여 미로를 표현
• 배열의 값이 0 : 갈 수 있는 길
• 배열의 값이 1 : 지나갈 수 없는 벽
• 출구 : x
• 현재 생쥐의 위치 : m

 

 

미로 탐색 프로그램

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