미로탈출( Maze Problem ) 해결과 이해 및 시간복잡도

소개

배열로 이루어진 미로( Maze ) 의 입구에서 출구까지의 경로를 구하는 프로그램의 소스입니다. 미로의 크기는 일정하게 정해놓은 상태로, 미로의 크기와 미로배열의 성분을 직접 수정하면 이전의 경로와 다른 새로운 경로를 출력할 수 있습니다.

미로배열을 출력할 때는 콘솔에서 색을 출력할 수 있도록 구현하여,
미로의 바깥벽은 녹색으로 출력하고, 이동할 수 있는 장소는 파란색, 입구에서 출구까지의 경로는 빨간색으로 출력하도록 하였습니다.( 실행화면 참고 )

재귀함수를 사용한 BackTracking 기법을 적용하여 경로를 찾도록 하여 불필요한
경로탐색을 하지않도록 하였고, 한번 탐색되었을 때 미로의 원래 배열값을
수정하도록 하여 한번 갔던 장소를 불필요하게 여러번 들르지 않도록 하고,
이 방법을 사용하여, 입구에서 출구까지의 경로중 원형 경로가 존재하는 경우
환형구조( Cycle ) 가 생기지 않도록 하였습니다.

단점은 탈출경로를 두개 이상 설정하는 경우엔 결과가 부정확할 수 있습니다.
경로를 찾게되면 경로를 바로 출력하는 방식이 아닌, 출구까지의 경로를 일단 저장하고, 그 경로를 이용해 원래의 미로배열값을 수정한 후, main() 함수에서 이를
출력하도록 한 구조이기 때문에 이같은 오류가 발생합니다.

요청이 있을 경우, 코드를 수정하여 출구를 찾으면 곧바로 출력하도록 수정합니다.

컴파일 실행환경

Microsoft Visual Studio 2008 C ( ENG Ver. )

참고자료

· 없음