스택의 활용 - 미로 탐색

참고 문헌

<C언어로 쉽게 풀어쓴 자료구조 내용 >

 

설명

미로에서 탈출하기 위해서는 미로를 체계적으로 탐색하여야 할 것이다.

출구를 찾는 기본적인 방법은 시행 착오 방법으로서 하나의 경로를 선택하여 한 번 시도해보고

안되면 다시 다른 경로를 시도하는 것이다.

문제는 현재의 경로가 안 될 경우에 다른 경로를 선택해야 한다는 것으로 가능한 경로들이 어딘가에 저장되어 있어야 한다.

그리고, 현재 위치에서 가능한 경로 중에서 가장 가까운 경로이면 좋을 것이다.

따라서 가능한 경로들이 저장되는데 그 중에서 가장 최근에 저장한 경로가 쉽게 추출되는 자료구조를

사용해야 할 것이다.

따라서 결론은 "스택"이 후보가 된다.

현재 위치에서 갈 수 있는 칸들의 좌표를 스택에 기억하였다가 막다른 길을 만나면 가장 가깝고,

아직 가보지 않은 칸으로 다시 돌아가서 새로운 경로를 찾아보는 것이다.

그리고, 한번 지나간 칸을 다시 가면 안된다.

이것은 각 방들을 지나갈 때마다 그 방에 방문된 것으로 표시를 하면 된다. 

 

현재위치에서 이동이 가능한 칸들의 위치를 위,아래,오른쪽,왼쪽의 순서로 스택에 저장하고

스택에서 맨위의 위치를 꺼내어 현재의 위치로 한 다음에 같은 작업을 반복한다.

이러한 반복은 현재의 위치가 출구와 같거나 모든 위치를 다 검사해볼 때까지 계속된다.

그리고 한 번 거쳐간 위치를 다시 검사하지 않도록 이미 검사한 위치는 표시를 하여 무한 루프에 빠지지 않도록 한다.

 

미로는 어떻게 만들까? 미로는 2차원 배열을 이용하자.

배열의 값이 ' '이면 갈 수 있는 길이고, '#'이면 지나갈 수 없는 벽을 의미한다.

출구는 'G'로 표시되고, 시작 위치는 'S'로 표시하자. 

 

알고리즘

위치는 ( 행, 열 )의 좌표값으로 표시한다. 따라서 스택에 저장되는 데이터는 ( 행,열)좌표가 되어야 한다. 

그래서, (행,열)좌표를 저장할 수 있는 구조체를 하나 만들자.

우리가 만든 스택의 기본적인 부분을 수정할 필요가 있다.

그리고 방문이 끝난 위치는 '.' 으로 바꾸어서 다른 위치들과 구분이 되게 한다.

그리고 스택이 비어있는데도 출구를 찾지 못했다면 미로 탐색은 실패를 의미한다.

 

미로탐색 알고리즘 수도 코드

 

자료구조 정의

스택은 앞에서 구현한 것을 그대로 가지고 온다.

다만 스택에 저장할 데이터는 행과 열을 표현할 구조체 변수를 저장한다.

구현

아래의 함수는 위의 미로 탐색을 실제로 수행하는 함수이다.

탐색에 필요한 나머지 함수들은 다음과 같다.

아래는 미로를 표현한 이차원 배열

아래는 메인 함수

프로그램 실행결과

 

소스 파일

common.h

0.00MB

main.c

0.00MB

mapInfo.c

0.00MB

mapInfo.h

0.00MB

MyStack.c

0.00MB

MyStack.h

0.00MB

point.h

0.00MB

 

아래의 미로 탐색 구현도 보도록 하자.

designatedroom87.tistory.com/70?category=882735

미로 탐색