stack을 응용한 미로찾기 구현 (알고리즘, 소스코드, 실행화면)

소개

본 과제에서는 stack을 응용한 미로찾기를 구현하여 보았습니다. class Bag을 이용하여 stack.h 코드를 작성한 후 실질적인 미로찾기 프로그램을 작성하였으며 자세한 미로찾기 알고리즘 설명 및 소스코드, 실행화면을 담고 있습니다.
우선 기본적으로 좌측과 같은 미로가 있다고 했을 때 갈수 있는 길은 0으로 표기하고 갈수 없는 벽은 1로 표시하는 배열을 사용하였습니다.
처음 시작과 출구의 경우 0으로 세팅하였으며 이러한 모든 맵은 프로그램 실행 시 항상 랜덤으로 나올 수 있도록 램덤함수를 사용 하여 0과 1이 랜덤하게 출력되게 하였습니다.
실질적으로 미로를 찾는 과정은 크게 3가지로 구성되어 있습니다. 첫 번째, 현재 위치에서 인접한 위치 중 갈수 있는 길이 있는지 확인하는 과정, 두 번째, 길이 있다고 하였을때 이동하는 과정, 그리고 마지막으로, 길이 없을 때 다시 돌아나오는 과정이 있습니다. 각 과정에 대한 세부적인 알고리즘역시 레포트에 자세하게 구현되 있습니다.

목차

1. 프로그램 설명
1.1 맵 만들기
1.2 길 찾기

2. 프로그램 소스코드
2.1 stack.h
2.2 themaze.cpp

3. 실행화면
3.1 길을 찾았을 경우
3.2 길이 없을 경우

본문내용

...
두번째 확인 결과 길이 있을 경우. 전진!
위의 첫 번째 과정에서 길이 있다고 판명되었을 경우에는 아래 3가지 순서로 전진과정이 실행되게 됩니다.
① 현재위치를 stack에 push함
② 목적지로 이동함 (현재위치를 새위치로 업데이트)
③ 새로이동한 위치를 “2”로 표시
따라서 위와 같은 과정으로 미로찾기가 진행되었을 경우 입구에서 출구까지의 찾은 길은 2로 표시되게 됩니다.

세 번째, 확인 결과 길이 없을 경우. 후진!
위의 첫 번째 과정에서 길이 없다고 판명되었을 경우에는 아래 순서로 후진과정이 실행되게 됩니다.
① stack에서 이전위치를 pop함
② 만약 stack이 Empty이면 길이 없는 걸로 판명되어 미로찾기가 끝남.
③ stack에 data가 있다면 현재위치를 “3”으로 표시
④ 이전위치로 이동 (현재위치를 이전위치로 업데이트)
위와 같은 과정으로 미로 찾기가 진행되었을 경우 잘못들어간 길은 3으로 표시되게 됩니다.
...

void main(){

int maze[12][12];


srand(time(NULL));

for(int i=0;i<12;i++){
maze[0][i] = 1;
maze[11][i] = 1;
maze[i][0] = 1;
maze[i][11] = 1;
}

for(int i=1;i<11;i++){
for(int j=1;j<11;j++){
int temp;
temp = rand()%5;
if(temp==0||temp==1||temp==2)
maze[i][j] = 1;
else
maze[i][j] = 0;
}
}
maze[1][1] = maze[10][10] = 0;
...

참고자료

· 없음