[C로 쓴 자료구조] 미로찾기

미로찾기

 

2차원 배열을 이용한 미로의 구현

maze[row][column]: 0 – 길, 1 – 벽

이동 방향 : 8방향(N, NE, E, SE, S, SW, W, NW)

 

경계 지역 : 8방향이 아님. (모서리: 3방향, 변: 5방향) 

m x p 미로를 (m + 2) x (p + 2) 미로로 변환

 

각 경계 영역의 maze 배열값은 1로 설정 

입구: maze[1][1], 출구: maze[m][p]

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100 // = m x p 
#define FALSE 0
#define TRUE 1
#define EXIT_ROW 4 // 출구 좌표
#define EXIT_COL 4

struct element{
	short int row;
	short int col;
	short int dir;
};
element stack[MAX_STACK_SIZE]; //내가 지나온 길을 저장하는 Stack

struct offsets {
	short int x;
	short int y;
};
offsets move[8]; //8개의 방향으로 이동

void init() {

	move[0].x = -1; //N
	move[0].y = 0;
	move[1].x = -1; //NE
	move[1].y = 1;
	move[2].x = 0; //E
	move[2].y = 1;
	move[3].x = 1; //SE
	move[3].y = 1;
	move[4].x = 1; //S
	move[4].y = 0;
	move[5].x = 1; //SW
	move[5].y = -1;
	move[6].x = 0; //W
	move[6].y = -1;
	move[7].x = -1; //NW
	move[7].y = -1;
}

int mark[6][6] = {0,}; //방문한 지역 check
int maze[6][6] = {
	1,1,1,1,1,1,
	1,0,0,1,0,1,
	1,0,0,1,1,1,
	1,1,0,1,1,1,
	1,1,0,0,0,1,
	1,1,1,1,1,1
};

int top = 0;

void full_stack() {

	printf("stack is full");
	return;
}

void push(element position) {

	if (top >= MAX_STACK_SIZE) {
		full_stack();
		return;
	}
	stack[top++] = position;
	return;
}

element pop() {
	if (top < 0) {
		
		element foo;
		foo.col = 0; foo.dir = 0; foo.row = 0;
		return foo;
	}
	return stack[--top];
}


void path(void)
{	// 미로를 통과하는 경로가 존재할 경우, 이를 출력
	int i, row, col, next_row, next_col, dir;
	int found = FALSE;

	element position;
	// 미로의 입구좌표와 E 방향으로 stack 초기화
	mark[1][1] = 1; 
	top = 0;
	stack[0].row = 1; stack[0].col = 1; stack[0].dir = 2; // 동쪽

	while (top > -1 && !found) { // stack이 empty가 아니고, 아직
		// 경로를 발견 못할 때까지 실행
		position = pop(); // top의 위치로 이동
		row = position.row; 
		col = position.col;
		dir = position.dir;

		while (dir < 8 && !found) { // 8방향을 차례대로 검사
			next_row = row + move[dir].x; // move in direction dir
			next_col = col + move[dir].y;

			if (next_row == EXIT_ROW && next_col == EXIT_COL)
				found = TRUE; // 출구 발견. 경로는 Stack에 저장되어 있음

			else if (!maze[next_row][next_col] && !mark[next_row][next_col]) { // 아직 안 가본 길
				mark[next_row][next_col] = 1;
				position.row = row;
				position.col = col;
				position.dir = ++dir;

				push(position); // 현재 좌표와 방향을 stack 저장
				row = next_row; // 안 가본 길로 전진. 방향은 북쪽
				col = next_col;
				dir = 0;
			}
			else ++dir;
		}
	}

	if (found) { // stack에 저장된 경로 출력
		printf(" The path is: \n ");
		printf("row col \n");
		for (i = 0; i <= top-1; 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(" The maze does not have a path \n ");
}

int main(void) {

	init();
	path();

}

 

 

실행결과