3-3강 - Mazing Problem (미로 문제)

cf> 미로는 stack의 좋은 응용이 될 것이다.

 

5. Mazing Problem

 

1) 미로 표현 방법

1> 미로 구조

- 미로 전체는 Two-dimensional array로 표현한다. ( maze[R][C] )

- 그리고 이동 가능한 길을 0, 벽을 1로 표현한다. 

- 미로 경계를 표현하기 위해 ( maze[R+2][C+2] )

• 행과 열을 2개씩 더 확보하고 
• 경계 부분을 1로 표시한다.

 

- 미로의 입구는 [1][1]이며 미로의 출구는 [R][C]이다.

 

2> 이동 방향

- 기본적으로 8개 방향으로 이동 가능하다.

• x방향과 y방향을 가지는 구조체 생성
• 8개의 구조체(원소)를 가지는 구조체 array 생성

- 하지만 [row][col] 주변에 경계 혹은 벽이 있을 경우 이동 가능한 방향이 적어질 수 있다.

typedef struct {
	short int vert;
	short int horiz;
} offsets;

offsets move[8]; /*array of moves for each direction*/

3> 미로 내부 이동 구현 (index 이용)

- 현재 위치 : [row][col] / 현재 위치의 상태 : maze[Row][Col]

- 다음 위치 : [nextRow][nextCol] / 다음 위치의 상태 : maze[nextRow][nextCol]

• nextRow = row + move[dir].vert
• nextCol = col + move[dir].hori

4> 방문 여부 기록

- 방문 여부 : mark라는 Two-dimensional array에 기록

 

cf> stack의 적용 : 입장부터 현재까지의 위치를 stack에 기록한다.

- 미로를 이동할 때에는 여러 방향의 선택이 있을 수 있다. 이때 어떤 방향이 최상의 선택인지 알 수 없으므로,현재의 위치를 저장하고 선택할 수 있는 한 방향을 선택한다. 이렇게 현재의 위치를 저장하면 만약 잘못돈 길을 갔을 때 되돌아와서 다른 방향을 시도 할 수 있다.

 

5> stack의 구현

- 이동 경로를 element라는 단위별로 쪼개서 저장한다. (element array = stack = 전체 이동경로)

- element : 위치와 이동경로를 한 번에 저장하는 구조체 

• row, col : 이동 경로 상에서의 위치 (행과 열)
• dir : 다음에 이동한 방향

- 그리고 element들의 array를 stack으로 정의한다.

- stack의 원소의 개수는 미로 탐색 중 방문하는 위치이면 충분

(미로 내의 0의 개수이면 충분 -> 최악의 경우를 고려해 mXp array의 경우 m*p개의 원소를 선언하면 충분하다.)

 

 

2) 구현 - 먼저 선언할 것

1> declare constant

- EXIT_ROW(EXIT_COL) : maze의 경계선을 제외한 행의 개수 = maze에서 출구의 행 index

- MAX_STACK_SIZE : 이동 경로를 기록할 stack(element array)의 최대 원소 개수

- TRUE, FALSE : 각각 1과 0

 

2> global variable

- top : 이동 경로를 기록할 stack의 top (가장 최근 이동경로가 저장된 index)

 

3> struct

- offset : 이동 방향 8개를 간단히 저장하기 위한 구조체 (북쪽 방향부터 시계방향으로 8개 방향)

- element : 위치와 이동경로를 한 번에 저장하는 구조체 

• row, col : 이동 경로 상에서 위치(행과 열)
• dir : 다음에 이동한 방향 

4> array

- stack : 이동 경로 전체를 저장 (element를 MAX_STACK_SIZE개의 array 형태로 저장)

- move : 이동 방향(offsets) 8개를 array로 저장

- maze : 미로의 경계선까지 포함한 미로의 구조

• 미로 자체의 크기는 maze[EXIT_ROW][EXIT_COL]이지만 경계선을 포함해서 maze[EXIT_ROW+2][EXIT_COL+2] 선언
• 0은 이동 가능한 공간, 1은 벽을 의미
• 경계 또한 1로 초기화한다.

- mark : 방문 여부를 기록할 array (maze와 크기가 같게 만든다.)

 

5> 추가적으로 필요한 함수

- element pop() : stack의 마지막 원소를 return하고 top 1감소(element 제거)

- void push(element cur) : top 1 증가 (새로운 원소를 추가할 공간 생성)하고 새로운 원소 추가

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100 /* maximum queue size */
#define EXIT_ROW 3 // maze 경계선 제외 행의 개수 = maze 출구의 행 index
#define EXIT_COL 3 // maze 경계선 제외 열의 개수 = maze 출구의 열 index
#define FALSE 0;
#define TRUE 1;

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

element stack[MAX_STACK_SIZE];

typedef struct {
	short int vert;
	short int horiz;
} offsets;

offsets move[8] = { {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1} };
/*array of moves for each direction*/

int maze[EXIT_ROW + 2][EXIT_COL + 2] = { {1,1,1,1,1}, {1,0,0,0,1}, {1,0,1,1,1}, {1,0,0,0,1}, {1,1,1,1,1} };
int mark[EXIT_ROW + 2][EXIT_COL + 2]; // 모두 0으로 초기화
int top;

element pop() {
	return stack[top--];
}
void push(element cur) {
	stack[++top] = cur;
}

 

3) 구현 - 함수 내부

1> local variable

- row, col : 현재 maze에서 위치하는 공간

- nextRow, nextCol : 다음 순서에 이동할 공간

- dir : 다음에 이동할 방향

- position : (element 자료형) 현재 이동 경로 (현재 위치와 다음에 이동할 방향 정보 저장)

 

2> 초기화

- top : stack에서 삽입과 삭제가 일어날 곳 / 0번째 element부터 시작 (지금 몇 번째 경로를 탐색하고 있는지)

- found : 출구를 발견했는지 여부 / 맨 처음에는 출구를 발견한 게 아니니 FALSE로 초기화 (1번째 loop를 깨는데 사용)

- 첫 번째 위치에 방문 : mark에 표시 (mark[1][1]의 값을 1로 변경)

- 이동 경로 저장 : stack의 0번째 element

• row와 col은 각각 1이다.
• dir은 미정이지만 임의로 1을 넣는다. (어짜피 북쪽 방향은 이동할 수 없다.)

3> 첫 번째 loop : top이 -1 초과 && found가 0이면 계속 돌아간다 (출구를 찾아서 found가 1이면 멈춘다.)

pop() -> position에 저장 -> 2번째 loop

- stack에서 top에 있는 원소를 가지고 2번째 loop을 진행한다.

• pop으로 top에 있는 원소를 return하고 잠시 stack에서 제거한다.
• position에 저장 => position에 있어야 2번째 loop을 진행한다.

4> 두 번째 loop : 8개 경로가 모두 열려 있으면 계속 돌아간다. (8개 경로 모두 막혀있으면 중단)

- 다음 위치를 만들고 다음 위치가 가질 수 있는 3가지 경우 중 어느 곳에 해당하는지 확인

• 1. 출구에 도착
• 2. 이동할 수 있는지 = 다음 위치가 비어있고 && 방문한 적이 없는지 (maze가 0이고 mark도 0인지)
• 3. 이동 불가능한 경우로 방향 변경 (dir을 증가시킨다.

- if : 출구에 도착했는지 확인하고 -> found를 TRUE로 변경 -> 첫 번째 loop 해제

- else if : 이동할 수 있는지 확인하고 

• 방문했다고 기록 (mark로 기록)
• stack에 저장할 position을 기록한다. (현재 row와 col 기록) (dir은 backtracking을 고려해서 나중에 돌아왔을 때 다른 direction으로 갈 수 있게 1을 증가시켜둔다.)
• position을 이동 경로로 저장 (stack에 push) (다른 곳으로 이동하니 경로가 된 것이고 stack에 저장한다.)
• 다시 row, col, dir 초기화 한다. (row와 col은 nextRow와 nextCol로 초기화) (dir은 0으로 초기화)

- else : 이동이 불가능한 경우이니 dir을 증가시켜서 방향을 변경해본다.

 

5> found가 TRUE로 변경되고 2개의 loop가 해제되며 종료된다. 

 

void path(void)
{
	/* output a path through the maze if such a path exists */
	int row, col, nextRow, nextCol, dir, found = FALSE;
	element position;
	mark[1][1] = 1; top = 0;
	stack[0].row = 1; stack[0].col = 1; stack[0].dir = 1;
	while (top > -1 && !found) {
		position = pop();
		row = position.row; col = position.col, dir = position.dir;
		while (dir < 8 && !found) {
			/* move in direction dir*/
			nextRow = row + move[dir].vert;
			nextCol = col + move[dir].horiz;
			if (nextRow == EXIT_ROW && nextCol == EXIT_COL) { 
				found = TRUE; 
			}
			else if (!maze[nextRow][nextCol] && !mark[nextRow][nextCol]) {
				mark[nextRow][nextCol] = 1;
				position.row = row; position.col = col;
				position.dir = ++dir;
				push(position);
				row = nextRow; col = nextCol; dir = 0;
			}
			else ++dir;
		}
	}
	if (found) {
		printf("The path is : \n");
		printf("row col \n");
		for (int i = 0; i <= top; i++)
			printf("%2d %5d", stack[i].row, stack[i].col);
		printf("%2d %5d \n", row, col);
		printf("%2d %5d \n", EXIT_ROW, EXIT_COL);
	}
	else printf("The maze does not have a path \n");
}

int main() {
	path();
	return 0;
}

 

6> 결론 

미로의 크기는 함수 path의 연산 시간을 결정한다. 미로의 각 위치는 한 번만 방문되므로 최악의 경우 연산 시간은 O(mp)이다. 여기서 m, p는 각각 미로의 행과 열이다

 

 

 

<전체 코드>

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100 /* maximum queue size */
#define EXIT_ROW 3 // maze 경계선 제외 행의 개수 = maze 출구의 행 index
#define EXIT_COL 3 // maze 경계선 제외 열의 개수 = maze 출구의 열 index
#define FALSE 0;
#define TRUE 1;

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

element stack[MAX_STACK_SIZE];

typedef struct {
	short int vert;
	short int horiz;
} offsets;

offsets move[8] = { {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1} };
/*array of moves for each direction*/

int maze[EXIT_ROW + 2][EXIT_COL + 2] = { {1,1,1,1,1}, {1,0,0,0,1}, {1,0,1,1,1}, {1,0,0,0,1}, {1,1,1,1,1} };
int mark[EXIT_ROW + 2][EXIT_COL + 2]; // 모두 0으로 초기화
int top;

element pop() {
	return stack[top--];
}
void push(element cur) {
	stack[++top] = cur;
}

void path(void)
{
	/* output a path through the maze if such a path exists */
	int row, col, nextRow, nextCol, dir, found = FALSE;
	element position;
	mark[1][1] = 1; top = 0;
	stack[0].row = 1; stack[0].col = 1; stack[0].dir = 1;
	while (top > -1 && !found) {
		position = pop();
		row = position.row; col = position.col, dir = position.dir;
		while (dir < 8 && !found) {
			/* move in direction dir*/
			nextRow = row + move[dir].vert;
			nextCol = col + move[dir].horiz;
			if (nextRow == EXIT_ROW && nextCol == EXIT_COL) { 
				found = TRUE; 
			}
			else if (!maze[nextRow][nextCol] && !mark[nextRow][nextCol]) {
				mark[nextRow][nextCol] = 1;
				position.row = row; position.col = col;
				position.dir = ++dir;
				push(position);
				row = nextRow; col = nextCol; dir = 0;
			}
			else ++dir;
		}
	}
	if (found) {
		printf("The path is : \n");
		printf("row col \n");
		for (int i = 0; i <= top; i++)
			printf("%2d %5d", stack[i].row, stack[i].col);
		printf("%2d %5d \n", row, col);
		printf("%2d %5d \n", EXIT_ROW, EXIT_COL);
	}
	else printf("The maze does not have a path \n");
}

int main() {
	path();
	return 0;
}