자료구조_스택을 활용한 미로찾기(대각선 이동 가능)

(Question) A mazing problem. How to solve the maze problem?

• Using the information provided in the text, write a complete program to search a maze. Print out the entrance to exit path if successful.

short maze[MAX_ROW][MAX_COL] = {

  {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},

  {1,START_POINT,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},

  {1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},

  {1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},

  {1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},

  {1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1},

  {1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},

  {1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1},

  {1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},

  {1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1},

  {1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},

  {1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,END_POINT,1},

  {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

} ;

 

0 : Through Path
1 : Blocked Path

You can find the following route with 8 directions.

	X

 

시각화된 미로

 

[알고리즘]

- 이미 방문한 위치를 표시하기 위해 새로운 배열 mark[13][17]을 만들어준다. (방문한 위치:1, 아직 방문하지 않은 위치:0)

- 현재 위치에서 일정한 규칙으로 다음 위치로 이동한다.

    -시계방향으로 이동가능한 위치 탐색(북, 북동, 동, 동남, 남, 남서, 서, 북서)

8	1	2
7	현재위치	3
6	5	4

   -그 방향으로 갈 수 있다면(아직 안가본 위치(mark[][]=0) & 벽이 아님(maze[][]=0)), 그 방향으로 이동

   - 아무 방향으로도 갈 수 없으면 그 위치에 오기 직전 위치로 되돌아간다.

 

[스택의 사용]

1.     현재위치는 출발점 ‘start_point’이다. 이 문제에서는 (1,1)

2.     다음을 반복한다.

3.     현재 위치에서 동,서,북,남,북동,남동,남서,북서 8방향에 대해 순서대로

        A.     그 방향으로 이동할 수 있는지(즉 벽이 아니고, 미로의 외부도 아니고, 이미 방문한 위치도 아닌지) 검사

        B.      만약 갈 수 있으면 현재 위치를 스택에 push하고 그 방향으로 이동

4.     만약 3번에서 4방향 중 어느 쪽으로도 갈 수 없었다면 스택에서 pop한 후 그 위치로 돌아간다. (만약 돌아갈 위치가 없다면 원래 길이 없는 미로이다.)

 

[실행 예시]

 

#include <stdio.h>
#define MAX_STACK_SIZE 100
#define FALSE 0
#define TRUE 1
#define EXIT_ROW 11
#define EXIT_COL 15

typedef struct {
	int vert; //수직좌표
	int horiz; //수평좌표
}offsets;

offsets move[8] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };//방향표시

typedef struct {
	short row;
	short col;
	short dir;
}element;

element stack[MAX_STACK_SIZE];

void path(void);
element pop(int*top);
void push(int*top, element position);
int top;
short maze[13][17] = {

  {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},

  {1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},

  {1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},

  {1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},

  {1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},

  {1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1},

  {1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},

  {1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1},

  {1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},

  {1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1},

  {1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},

  {1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1},

  {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

};

int mark[13][17] = { 0, };

void main() {
	path();
}

void path(void) { //경로가 있다면 패스 출력
	int i, row, col, next_row, next_col, dir;
	int found = FALSE; //1이면 출구
	element position;
	mark[1][1] = 1; //방문 표시(시작점)
	top = 0; //시작점 스택에 push
	stack[0].row = 1; stack[0].col = 1; stack[0].dir = 1;

	while (top > -1 && !found) {//stack에 path가 남아있으면서 출구를 못찾은 상태
		position = pop(&top); //스택에서 현위치를 pop
		row = position.row; col = position.col; dir = position.dir;

		//내 주변의 8방향을 찾아보기
		while (dir < 8 && !found) {
			next_row = row + move[dir].vert;
			next_col = col + move[dir].horiz;
			if (next_row == EXIT_ROW && next_col == EXIT_COL) {
				found = TRUE; //탈출 성공
			}
			else if (!maze[next_row][next_col]&&!mark[next_row][next_col]) {//다음위치가 0이면서 방문한 적이 없을 때
				mark[next_row][next_col] = TRUE;
				position.row = row; position.col = col; position.dir = dir;
				push(&top, position);//스택에 현재 위치 저장
				row = next_row;
				col = next_col;
				dir = 0;
			}
			else ++dir; //탈출도 아니며 갈수있는 곳이 없을 때(이미 방문했거나 벽이거나)
		}
	}
	if (found) {
		printf("<Path>\n"); //방문한 길 출력
		printf("row col\n");
		for (i = 0; i <= top; i++) {
			printf("%2d %5d\n", stack[i].row, stack[i].col);
		}
		printf("%2d %5d\n", row, col);
		printf("%2d %5d\n", EXIT_ROW, EXIT_COL);
	}
	else
		printf("no path found!!\n");//길이 없는 미로
}

void push(int*top, element position) {
	(*top)++;
	stack[*top].col = position.col;
	stack[*top].row = position.row;
	stack[*top].dir = position.dir;
}

element pop(int*top) {
	element result;
	if (*top < 0) {
		printf("Stack is Empty.\n");
	}
	else {
		result = stack[*top];
		(*top)--;
	}
	return result;
}

위 코드는 https://fascination-euna.tistory.com/34을 참고했습니다.

[DS] A Maze Problem (스택으로 미로 문제 풀기)

[실행결과]

<Path>
row  col
 1     1
 2     2
 1     3
 1     4
 1     5
 2     4
 3     5
 3     4
 4     3
 5     3
 6     2
 7     1
 8     2
 9     3
 9     4
 8     5
 7     6
 7     7
 8     8
 9     8
10     9
10    10
 9    11
 9    12
 9    13
 8    14
 9    15
10    15
11    15

미로찾기 결과