[ Qt 프로그래밍 ] 미로찾기 프로그램

maze15.txt

Maze2.txt

maze20.txt

Maze9.txt

미로찾기.exe

미로찾기는 시작점에서 출발해서 미로를 통과해 도착점까지 가는게 목표입니다.

만약 일직선이면 그냥 가면됩니다.

하지만 항상 갈림길이 나옵니다.

과연 이 갈림길에서 어떤 선택을 해야할까요?

이런점에서 많은 고민을 해봐야하는 프로그램입니다.

총 에너지는 미로의 행*열*2의 크기를 갖고있고 한칸씩 움직일때마다 1씩 감소합니다.

그리고 자신의 위치에서 주변을 둘러싸는 9칸까지는 벽인지 길인지 알수있습니다.

마지막으로 왼쪽위에서 출발해서 오른쪽아래 끝점으로 도착하는건 정해져있지만,

미로의 크기와 미로 데이터는 랜덤입니다.

미로는 정사각형이 아니라 직사각형일 수도 있습니다.

 

 

저는 미로찾기 프로그램을 짤때 간단한 몇가지 아이디어를 적용했습니다.

 

 

첫째로, 출발점과 도착점의 위치는 정해져있습니다. 따라서 어떤 미로든 출발점과 도착점을 잇는 대각선을 긋고, 갈림길을 만났을때, 대각선보다 위에있으면 아래쪽으로, 대각선보다 아래에 있으면 오른쪽으로 우선순위를 정해서 가도록 했습니다.

 

 

 

둘째, 위 그림에서 빨간색은 되돌아온 길, 초록색은 한번만 간길, 청록색은 안가도 길이 아닌걸 알수있는 지점입니다. 빨간색 선들이 청록색을 둘러싸고 있는 것이 보이실텐데, 이렇게 한바퀴 돌아서 환형구조로 폐구간을 만들면 직관적으로 봤을때 안쪽지역에서 도착지점으로 가는길은 없습니다. 따라서 굳이 들어가지 않고 나와버립니다.

 

 

셋째로, 위 그림에서 왼쪽위 출발점에서 대각선으로 내려오고 있는 초록색 점들이 보일겁니다. 그러다가 오른쪽으로 쭉가다가 위로 안올라가고 다시 돌아옵니다. 이는 미로 전체의 끝쪽 벽에 도착했기때문입니다. 출발점과 끝쪽 벽에 도착했을때 위로갔을때 도착점으로 갈수있는 길을 직관적으로 생각해도 없습니다. 그래서 굳이 안가고도 다시 돌아올 수 있습니다. 마찬가지로, 왼쪽으로 가다가 미로의 끝 벽에 도착했을때, 위로 간다해도 도착점으로 갈수없기때문에 청록색 점으로 길을 차단시켜 버립니다.

 

이렇게 간단한 세가지 아이디어를 토대로 Qt로 미로찾기 프로그램을 만들어 봤습니다.

 

위 사진은 200x200 크기의 미로입니다. 마치 세계지도를 보는것 같습니다.;

여기서 초록색 점들이 한번만에 도착하는 경로이고, 빨간색 점들은 갔다가 되돌아온 경로, 청록색 점들은 안가봐도 길이 아닌걸 알 수 있는 폐구간입니다.

 

첨부파일에 올려둘테니 한번 해보세요~

미로찾기.exe를 실행 한후, Maze#.txt를 선택하면 맵이 나타나는데, start를 누르면 미로찾기가 시작합니다.

아래 슬라이더는 speed는 미로찾기 속도 조절,  size는 미로찾기 확대/축소 입니다.

이상입니다