Data Structure - 스택을 이용한 미로 표현

티스토리 뷰

Development/Data Structure

Data Structure - 스택을 이용한 미로 표현

ShinyOcean 2021. 2. 17. 17:26

Data Structure(자료 구조)를 주제로 한 세번째 포스팅은 자료의 구조중 스택이라는 구조와 이 스택구조를 이용한 미로를 표현해 보겠습니다.

먼저 스택이란?

후입선출(Last In First Out—LIFO)의 형태를 가지고 있는 자료구조로써 아래의 그림과 같습니다.

메모리에 새로 들어오는 데이터의 위치가 그릇의 탑(꼭대기)이고, 써먹기 위해 내보내는 데이터 역시 꼭대기에 위치한다. 입력연산은 Push, 출력연산은 Pop이라고 부른다. 조회연산은 Peek라고 하는데, 탑 포인터가 가리키는 데이터를 확인만 할 뿐, 탑의 인덱스는 변화시키지 않는 연산을 의미한다.

위에서 설명했듯이 스택을 사용하기 위해서는 스택의 자료를 조작하기 위한 여러가지 함수(pop push ...)가 필요합니다.

C언어에서 스택을 표현하기위한 코드는 다음과 같습니다.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_SIZE_STACK 100 //스택의 크기를 최대 100으로 잡아줌

#define MAZE_SIZE 17 //17by16 2차원배열이라 17로 설정

typedef struct {

short r;

short c;

}element; //행과 열의 요소를 구조체로 만듬, 결과를 쌓을 스택

typedef struct {

element data[MAX_SIZE_STACK];

int top;

}StackType;

void init(StackType* s)

{

s->top = -1;

} //top 값을 -1로 초기화

int is_empty(StackType* s) {

return s->top == -1;

} //stack empty를 확인

int is_full(StackType* s) {

return s->top == MAX_SIZE_STACK - 1;

} //stack full을 확인

void push(StackType* s, element item) {

if (is_full(s))

{

fprintf(stderr, "스택포호에러\n");

return;

}

s->data[++(s->top)] = item;

} //stack에 item push

element pop(StackType* s) {

if (is_empty(s))

exit(1);

return s->data[(s->top)--];

} //stack에서 pop

element peek(StackType* s){

if (is_empty(s)) {

exit(1);

}

else return s->data[s->top];

} //peek

그럼 이제부터 스택 구조를 이용한 간단한 미로 시뮬레이션을 프로그래밍 해보겠습니다.

{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},

{'1','0','0','0','1','0','0','1','1','0','0','0','0','1','0','0','1'},

{'1','0','1','0','1','0','0','0','0','0','1','0','0','0','0','1','1'},

{'1','0','1','1','1','0','0','1','0','1','1','1','0','1','0','1','1'},

{'1','0','0','0','1','0','0','0','0','0','1','0','0','1','0','0','1'},

{'e','0','1','0','0','0','1','1','1','0','1','0','1','1','1','0','1'},

{'1','0','1','0','0','1','1','0','1','0','1','0','0','0','0','0','1'},

{'1','0','1','1','1','1','0','0','1','0','0','1','0','1','1','0','1'},

{'1','0','0','0','0','0','0','0','1','0','0','1','0','0','0','0','0'},

{'1','0','1','1','0','1','0','0','0','1','0','0','1','1','0','0','1'},

{'1','1','0','1','0','0','0','1','0','0','0','0','0','0','0','0','1'},

{'1','0','0','1','0','0','1','0','1','0','0','1','0','0','1','1','1'},

{'1','1','0','0','0','1','0','0','1','1','1','0','0','0','0','0','1'},

{'1','1','0','1','1','0','0','0','0','1','0','0','0','1','1','0','1'},

{'1','0','0','0','0','0','0','1','0','0','0','1','0','0','1','0','x'},

{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},

위와 같이 2차원 배열로 지도를 표현하였습니다. 현제 위치는 'e'이고 이동가능한 위치는 0 할수 없는 위치는1

도착지는 'x' 이동한 위치는 '.'을 통해 표현하는 규칙을 제 임의로 만들어 보았습니다

이제부터 풀이로 넘어가겠습니다.

기본적인 방법은 시행착오 방법으로 하나의 경로를 선택하여 시도해보고 안되면 인접한 다른 경로로 다시 시도 하는

것입니다. 문제는 현재의 경로가 안될 경우에 다른경로를 선택하야 한다는 것으로 다른 경로들이 어딘가에 저장되어

있어야 합니다, 이과정을 스택을 사용하여 표현후 목적지를 만날때까지 반복하는 것입니다.

이과정을 알고리즘으로 표현해보면

maze_search(){

스택 s와 출구의 위치 x, 현재위치 초기화

while(현재위치가 출구가 아니면) do

현재위치를 방문한 것으로 표기

if( 현재위치의 위, 아래, 왼쪽, 오른쪽 위치가 아직 방문되지 않았고 갈수 있으면)

then 그 위치를 스택에push

if(is_empty(s))

then 실패

else 스택에서 하나의 위치를 꺼내어 현재 위치로 만든다;

성공;

}

정도로 표현될수 있습니다, 위과정에서 방문이 끝난 위치는 배열의 값에 ‘.’으로 바꾸어 다른 위치들과 구별했습니다.

초기 시작점의 값(entry)의 좌표를 지도상 e의 위치인 {5,0}으로 설정했습니다.

알고리즘상 표현 while(현재위치가 출구가 아니면) do을 조건화하여

(maze[here.r][here.c] != 'x')로 설정하고 조건 만족시 “성공”을 출력후 종료되게 코딩해봤습니다.

전체 코드)

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_SIZE_STACK 100 //스택의 크기를 최대 100으로 잡아줌

#define MAZE_SIZE 17 //17by16 2차원배열이라 17로 설정

typedef struct {

short r;

short c;

}element; //행과 열의 요소를 구조체로 만듬, 결과를 쌓을 스택

------------------------------------------------------스택 함수

typedef struct {

element data[MAX_SIZE_STACK];

int top;

}StackType;

void init(StackType* s)

{

s->top = -1;

} //top 값을 -1로 초기화

int is_empty(StackType* s) {

return s->top == -1;

} //stack empty를 확인

int is_full(StackType* s) {

return s->top == MAX_SIZE_STACK - 1;

} //stack full을 확인

void push(StackType* s, element item) {

if (is_full(s))

{

fprintf(stderr, "스택포호에러\n");

return;

}

s->data[++(s->top)] = item;

} //stack에 item push

element pop(StackType* s) {

if (is_empty(s))

exit(1);

return s->data[(s->top)--];

} //stack에서 pop

element peek(StackType* s){

if (is_empty(s)) {

exit(1);

}

else return s->data[s->top];

} //peek

-------------------------------------------------스택함수

element here = { 1,0 }, entry = { 5,0 }; //시작점 재설정

char maze[MAZE_SIZE][MAZE_SIZE] = {