미로문제
- 마이크로 마우스가 하나의 입구에서 출발해서 여러 갈림길을 거쳐 하나밖에 없는 출구까지의 경로를 찾는 문제
- 진행을 하다가 막히면, 지나온 길을 되돌아가서 다시 진행하는 시행착오를 겪으면서 출구까지 이동
- 전체 이동 경로에서 시행착오 구간을 제외한 단일 경로를 찾는 것이 문제
문제 접근 방향
- 미로를 어떻게 표현해야 할까?
- 마우스의 이동을 어떻게 표현하고 그 기록을 어떻게 저장할 것인가?
- 총 이동경로는 24개
- 시행착오구간을 제외한 1,2,3,4,5,6,7,9,10.11,12,14,15,16,19,20,22,23,24
미로를 어떻게 표현할 것인가?
- 주어진 미로를 2차원 배열 7*6으로 표현
- 마우스의 위치는 X좌표와 y좌표를 갖는 구조체로 표현한다.
※ 미로표현에서의 문제점
- 마우스가 미로의 범위 밖으로 나가는 것을 막으려면 어떻게 해야 할까?
- 마우스의 좌표가 이동할 때, 미로의 범위 밖으로 이동하는 것을 막는 것도 고려해야 한다.
마우스가 미로의 범위 밖으로 나가는 것을 막으려면?
해결방법1
마우스가 이동할 좌표가 전체 배열 범위를 넘어서는지를 검사하여 만일 범위를 넘어서면 벽이 있다고 판단하여 이동하지 못하게 한다.
1번 방향은 지나온 좌표이므로 갈 필요가 없다.
2번 방향은 이동 후 좌표가 미로의 범위를 벗어나므로 진행할 수 없다.
3번 방향은 지나온 좌표도 아니고 이동 후 위치가 0이기 때문에 진행할 수 있음
4번 방향은 이동 후 위치가 1이기 때문에 진행할 수 없음.
해결방법2
- 벽도 하나의 좌표로 생각하고 벽을 모두 1로 표현하여 미로를 둘러싼다.
- 매번 마우스가 이동할 좌표가 범위 안에 있는 지를 검사하지 않아도 되므로, 프로그램이 단순하고 명확해진다.
- 결과적으로 m*n 크기의 미로는 (m+2)*(n+2) 크기의 배열이 된다.
좌표변경을 이용한 마우스의 이동 표현
스택을 이용한 마우스 이동
스택에 푸쉬
- 마우스는 동남서북의 순서로 이동가능성을 판단한다.
- 이동 가능성이 있는 방향이 발견될 경우 즉시 이동한다.
스택에서 팝
- 이동가능성이 있는 방향이 없을 경우에는 이전 위치로 돌아가서 이동가능성을 판단한다.
최종적으로 스택에는 시행착오 구간을 제외한 경로가 저장된다.
※ 이렇게 어떤 알고리즘 문제를 풀어야 할 때, 최종적으로 저장되어야 할 자료구조의 형태를 정하면 알고리즘을 짤 때 수월해진다.
미로의 정의
#define MaxRowSize 7
#define MaxColSize 6
// 미로 정의
int maze[MaxRowSize + 2][MaxColSize + 2] = {
{1,1,1,1,1,1,1,1},
{1,0,1,1,0,1,1,1},
{1,0,0,1,0,1,1,1},
{1,1,0,0,0,1,1,1},
{1,1,1,0,0,0,1,1},
{1,0,0,0,1,1,1,1},
{1,1,0,1,0,0,0,1},
{1,0,0,0,0,1,0,1},
{1,1,1,1,1,1,1,1}
};- 실제 배열의 크기인 7, 6으로 상수를 정한다.
- 그러나 배열 바깥에 1로 벽을 만들기 위해서 2씩 더한다.
마우스 및 스택 구조체 선언
typedef struct {
int x; // x좌표
int y; // y좌표
int dir; // 0동, 1남, 2서, 3북
}mouseType;
typedef struct {
int Top;
mouseType Stack[MaxRowSize * MaxColSize];
}stackType;- 마우스의 속성은 x, y 좌표와 방향값이다.
- 스택의 속성은 Top과 마우스 좌표다.
push 함수
void push(stackType* Sptr, mouseType Item) {
if (Sptr->Top >= MaxRowSize * MaxColSize) {
printf("더 이상 넣을 수 없습니다!\n");
}
else {
// Stack[Top+1]에 데이터 삽입 후 Top 1증가
Sptr->Stack[Sptr->Top + 1] = Item;
Sptr->Top = Sptr->Top + 1;
}
}스택 안에 스택이 들어가니, 포인터가 두 개가 되어 조금 헷갈린다.
pop 함수
mouseType pop(stackType* Sptr) {
mouseType temp;
if (Sptr->Top < 0) {
printf("스택이 비었습니다!\n");
}
else {
temp = Sptr->Stack[Sptr->Top];
Sptr->Stack[Sptr->Top] = Sptr->Stack[Sptr->Top - 1];
return temp;
}
}mouseType을 반환하는 것이므로 데이터타입을 정한다.
printStack 함수
void printStack(stackType* Sptr) {
int i;
if(Sptr->Top >= 0){
for (i = 0; i < Sptr->Top; Sptr->Top + 1) {
printf("<%d %d %d>\n",Sptr->Stack[i].x, Sptr->Stack[i].y, Sptr->Stack[i].dir);
}
}
}
마우스 이동 함수
#include <stdio.h>
#include "maze.h"
void initMouse(mouseType* Mouse) {
Mouse->x = 1; // 좌표 (1, 1)
Mouse->y = 1;
Mouse->dir = 0; // 방향 동쪽
}
void moveMouse(mouseType* Mouse) {
switch (Mouse->dir)
{
case 0: Mouse->y++; break; // 동
case 1: Mouse->x++; break; // 남
case 2: Mouse->y--; break; // 서
case 3: Mouse->x--; break; // 북
}
Mouse->dir = 0; // 방향 초기화
maze[Mouse->x][Mouse->y] = 1; // 현재 이동한 지점을 다시 가지 않도록 1로 표시
}
마우스 이동 가능성 검사
int movePossible(int x, int y, int direction) {
switch (direction)
{
case 0: y++;
case 1: x++;
case 2: y--;
case 3: x--;
}
if (maze[x][y] == 1) {
return 0; // false
}
else return 1; // true
}- 방향마다 검사를 했을 때, 배열 증감에 따라 좌표가 달라졌을 때 1 즉 벽을 만나면, 이동할 수 없으므로 0 반환, 반대의 경우 1을 반환한다.
void main(void)
{
stackType Path_Stack; // 경로 선택시 사용할 스택 정의
mouseType Mouse; // 미로를 찾을 마우스 정의
initStack(&Path_Stack);
initMouse(&Mouse);
push(&Path_Stack, Mouse); // 처음 위치와 방향(1,1,0) 삽입
while (Path_Stack.Top >= 0)
{
Mouse = pop(&Path_Stack);
//시도 해볼 방향이 있는 한 계속 시도
while (Mouse.dir <= 3)
{
if (Mouse.x == 7 && Mouse.y == 6) // 목표 지점이 오면 종료한다.
{
push(&Path_Stack, Mouse); // 스택에 삽입
printf("마우스의 이동 경로는 다음과 같습니다.\n");
printStack(&Path_Stack);
exit(0);
}
else
{
if (movePossible(Mouse.x, Mouse.y, Mouse.dir) == 1)
{
push(&Path_Stack, Mouse); // 스택에 삽입
moveMouse(&Mouse); // 마우스 이동
}
else
{
Mouse.dir = Mouse.dir + 1; // 다음 이동할 방향을 설정
}
}
}
}
}마우스의 이동 경로는 다음과 같습니다.
<1, 1, 1>
<2, 1, 0>
<2, 2, 1>
<3, 2, 0>
<3, 3, 0>
<3, 4, 1>
<4, 4, 2>
<4, 3, 1>
<5, 3, 2>
<5, 2, 1>
<6, 2, 1>
<7, 2, 0>
<7, 3, 0>
<7, 4, 3>
<6, 4, 0>
<6, 5, 0>
<6, 6, 1>
<7, 6, 0>
미로를 바꿔보자
// 미로정의
int maze[MaxRowSize+2][MaxColSize+2] = {
{1,1,1,1,1,1,1,1}, // 1행
{1,0,1,1,0,1,1,1}, // 2행
{1,0,0,0,0,1,1,1}, // 3행
{1,1,0,0,0,0,0,1}, // 4행
{1,1,1,0,0,0,0,1}, // 5행
{1,0,0,0,1,1,0,1}, // 6행
{1,1,0,1,1,0,0,1}, // 7행
{1,0,0,0,0,1,0,1}, // 8행
{1,1,1,1,1,1,1,1}}; // 9행마우스의 이동 경로는 다음과 같습니다.
<1, 1, 1>
<2, 1, 0>
<2, 2, 0>
<2, 3, 0>
<2, 4, 1>
<3, 4, 0>
<3, 5, 0>
<3, 6, 1>
<4, 6, 1>
<5, 6, 1>
<6, 6, 1>
<7, 6, 0>