대학교 2학년때, 자료 구조 수업 시간의 두번째 레포트로 작성했던 프로그램입니다. 미로를 탈출하는 생쥐를 시뮬레이션 해 줍니다. 이 내용은 아래 레퍼런스 책으로 올라온 C++로 구현한 자료 구조 중에서 스택 부분에 나옵니다. 전체적인 요구 사항은 스택을 사용해서 백트래킹 알고리즘을 구현하는 것 입니다. 백트래킹으로 탐색하는 생쥐이기 때문에 매우 무식하게 미로를 탈출합니다. 직선 경로가 있는 경우도 돌아서 가는 경우가 많습니다.
책에서는 미로 생성에 관해서는 따로 언급하는 내용이 없습니다. 홈페이지에도 어딘가에 그 당시 생각을 끄적여둔 글이 있는 것 같은데,.. 아마도 특정 부분을 막는다는 개념으로 미로를 생성했던 것 같습니다. 생성 또한 단순하게 해서, 조금만 복잡하게 만드려고 해도 길이 없는 경우가 많습니다.
전체적으로 소스는 미로와 관련된 내용을 구현한 것들은 따로 파일로 분리되어서 보기 편할 겁니다. UI관련된 부분은 아주 지저분하게 작성되어져서 보기 힘들것 같군요.
Download
Reference Book
- C++로 구현한 자료 구조 - 명품이죠...
- Visual C++ Bible 6.X(영진) - 그 당시 유명한 책이었는데, 요즘은 악평이 많은 책이죠.
- Visual C++ Bible 6.X(삼양) - 요즘 호평을 받고 있는 책입니다.
첫번째 그림은 프로그램 초기 화면 입니다. 허접한 로고가 있던 부분을 이번에 홈페이지에 올리면서 레이싱 걸, 최혜영님 사진으로 바꾸었습니다. ㅎㅎ^^ 왼쪽 상단에 있는 입력 창이 각각 미로의 가로, 세로 크기와 미로를 생성하는데 필요한 시드를 입력하는 곳 입니다. 미로를 생성하는 알고리즘은 그 당시 대충 생각나는 대로 작성한 것입니다. 시드는 2에서 미로 크기 보다 3 작게 입력해야 하는 것 같네요. 시드가 클 수록 복잡한 미로가 생성됩니다.
미로 생성 버튼을 누르면, 입력한 정보에 맞게 미로가 생성 됩니다. 그런 다음 길찾기 버튼을 누르게 되면, 쥐돌이가 열심히 미로를 찾게 됩니다. 미로를 찾은 경우는 왼쪽 화면과 같이 붉은 색으로 자신이 찾은 경로를 출력해 줍니다. 중간에 삽질한 부분에 대한 이동 경로는 출력하지 않습니다.
중간 부분의 시뮬레이션 도구를 사용하시면 쥐돌이가 실제로 어떻게 이동했는지를 보여줍니다. 슬라이드 바는 쥐돌이가 한 칸을 이동하는데 걸리는 시간을 나타냅니다. 오른쪽으로 옮길수록 쥐돌이는 천천히 움직입니다. 시간 간격을 선택한 후에 시작 버튼을 누르면 파란색 사각형으로 나타나는 것이 쥐돌이의 위치입니다. 한 칸씩 움직이는 것을 볼 수 있을 겁니다.