[자료구조] Stack으로 구현한 미로찾기 (Rat In Maze)

목차

<b>1. 프로그래밍 감상문.hwp</b>
Data Structure and Algorithm In JaVa
'Rat In Maze' with Stack
1. 알고리즘
2. 수행 결과
3. 프로그래밍 후기
<b>2. RatInMaze.cpp
3. maze.txt</b>

본문내용

1. 알고리즘
>> 이번 프로그래밍 리포트의 주제는 스택을 이용한 미로 속에서 길 찾기입니다.
일단 미로를 찾기 위해서는 시작점과 종료지점을 알고 그 사이에서 이동 가능한 범위를 생각하여 검사-수행의 과정을 거쳐 길을 찾아내는 방법을 사용합니다.
이 과정에서 스택은 지나온 길에 대한 정보를 차곡차곡 저장해 두었다가 벽에 부딪혀 리턴할 경우에 다음 오퍼레이션에 대한 정보를 줄 수 있습니다.
이런 문제를 해결하기 위해 전 다음과 같은 알고리즘을 사용하였습니다.
1. 미로를 외부로부터 입력 받는다.
2. 그 미로를 일단 보여 준다.
3. 각 지점에서 행할 수 있는 움직임은 4방향이며 가장자리에서는 2방향 또는 3방향 밖에 행할 수 없는 문제점을 해결하기 위해 전체 매트릭스 주위에 한 겹의 벽을 쌓는다.
4. 준비된 미로 매트릭스의 출발점을 알고 길 찾기 수행을 시작한다.
5. 일단 우선순위의 움직임을 행한다. 한 칸 움직일 때마나 지나온 길에 대한 정보를 스택에 저장하고 현제 위치에 대한 정보는 다른 구조체에 저장한다.
6. 한 방향으로 움직이다가 더 이상 나아갈 수 없다는 조건에 부딪혔을 때 다른 길을 모색한다. 이를 위해 저장해 두었던 스택의 정보를 위에서부터 차례대로 꺼내어 계속 다른 길을 찾아 나간다.
7. 종료 지점에 이르렀을 때, 프로그램의 완료를 알리고 오퍼레이션을 멈춘다.
8. 길을 출력한다.
* 이 과정을 수행하는 중에 스택의 언더 플로우나 오버 플로우 와 같은 오류 처리를 수행할 수 있도록 한다.

참고자료

· 없음