[자료구조] 생쥐의 미로 찾기 (우선법 알고리즘)

second_array.exe

second_array.cpp

Rat.h

책을보다가 흥미로운 문제가 주어져서 직접 구현해봤습니다.
실행파일이 제대로 돌아갈지 모르겠네요
코딩된 환경은 비쥬얼 스튜디오 2008입니다.

이 글을 보실때에
기본적으로 링크드리스트(Linked List)에 대해 이해가 있어야할것 같습니다.
C언어 상태로 짰습니다..

책에서 우선법을 봤는데..
우선법은 어떤 미로든지 오른손을 벽에 대고 가다보면 언젠간
도착지에 도달할수 있다라는 개념입니다.
서울대 학생분들이 이 알고리즘을 썼다고 합니다.
대단합니다~
미로를 빠져나간 경로를 알고있다면 우선법으로 갔던길의
최단거리를 도출할수 있습니다.
좌표가 같은 구간(즉, 들어갔다가 다시 제자리로 나온) 사이 경로를
모두 삭제하는겁니다. A B C B F E 이런식이라면..
B와 C를 삭제하는겁니다.. 안으로 들어갈 필요가 없는거죠.

제 소스에선 19 X 19 배열안에 맵을 저장시켜놓았습니다.
0은 길, 1은 벽, 5는 생쥐로 정했습니다.
쥐의 좌표 x, y 값과 dir이라고 정의되있는건 방향(Direction)입니다.
main함수에서 첫번째 while문을 돌면서 우선법으로 이동합니다.
이동하는 동시에 Record_Mouse함수가 리스트를 늘려가면서 이동
경로(x, y, dir)를 저장합니다.
그리고 Short_Way함수에서 이미 Record_Mouse에서 저장시켜논
링크드리스트(Linked List)안에서 최단거리를 도출합니다.

main안에 두번째 while문은 최단거리가 된 리스트를 순서대로
찍어주기만 한겁니다.
스파게티소스가 되버렸는데.. 참고하시길 바래요..



ps.
많은 분들이 그냥 긁어가시는 분들이 많은데..
긁어가시는건 자유지만.. 그러면 실력이 잘 안늘더라구요..
실행파일 소스파일 헤더파일 포함했습니다
혹여 이해안가시면 댓글달아주세용