스택구조_미로 찾기 [1/3]

이번 과제는 미로 찾기입니다. 두 달 가까이 열심히 공부했더니 이제 이정도는 꽤 순조롭게 짤 수 있게 됐네요. 왕기초 과제이지만 왕초보인 저는 아직은 이정도만해도 뿌듯.. 뭔가 애니메이션같이 진행되는 모습을 보고 싶은데 방법이 없나 내일 한 번 찾아봐야겠어요. 과정마다 하나씩 프린트할 수는 있지만 영 맘에 들진 않네요..ㅎㅎ

해당 과제는 유투브 '권오흠'님의 자료구조 강의를 참조하였습니다.

 

 

---

 

[ main() ]

• 사실 이번 건 코딩보다 미로 그리는게 더 어려웠던 것 같음..
• 미로크기는 언제든 변경할 수 있게 매크로를 사용
• 배열 내용이 낭비없는 구성이라 포인터 변수 배열 대신 일반 배열을 사용함
• 이동할 수 있는 최대값인 MAX는 ROW * ROW * 2 로 설정

#include <stdio.h>
#include <stdlib.h>
#define MAX 128
#define ROW 8
#define COL 17

typedef struct {
	int row;	// 세로 위치 (위, 아래)
	int col;	// 가로 위치 (좌, 우)
}location;

int maze_runner(char maze[][COL]);
location* new_location(int* w);
location* push(location* way[], int* w, int row, int col);
void pop(location* way[], int* w);
int iswhat(char maze[][COL], int row, int col);
int dir_check(char maze[][COL], location* a);
void footstep(char maze[][COL], location* a);
void backstep(char maze[][COL], location* a);
void finalstep(char maze[][COL], location* a);
void maze_print(char maze[][COL]);

void main()
{
	/*미로 그림 만들기 */
	char maze[][COL] =
	{	
		"□□■□□□□□",
		"□■■□■■■■",
		"□■□□■□□□",
		"□■□■■□■■",
		"□□□□□□□□",
		"■■■□□■■■",
		"■■□□□■□□",
		"□□□■□□□□",		
	};
	
	if (maze_runner(maze) == 0)
		puts("길이 없습니다...");
	
	maze_print(maze);
    printf("\n출구를 찾았습니다.\n");
}

 

---

 

[ int maze_runner() - 최종 길찾기 ]

• if (d == 0) 구절을 switch문으로 바꿀 수도 있지만, 줄이 더 길어져서 그냥 if문 사용
• 보통 조건이 3~4개 사이는 if문이, 그 이상은 switch가 속도가 더 빠르다고 함
• 하지만 컴파일러마다 다르고 속도차이가 크지 않기 때문에 일반적으로는 가독성이 더 중요할듯

/* 미로찾기 */
/* parameter : 미로 배열 */
/* return : 정상종료 == 1, 비정상종료 == 0 */
int maze_runner(char maze[][COL])
{
	/* 지나간 길 저장할 스택(배열)과 저장갯수 */
	static location* way[MAX] = { NULL };
	static int w = 0;

	/* 북쪽부터 시계방향으로 돌림 (최대한 빨리 못찾게..) */
	/* 현재 위치 저장 변수 */
	location* a;
	a = push(way, &w, 0, 0);  // 출발지 생성
	int d = 0;  // 방향확인 후 return 받을 변수
	
	while (1)
	{
		/* 메모리 할당에 실패했을 경우 */
		if (a == NULL)
		{
			puts("미로가 이상합니다..ㅠㅠ");
			return 0;
		}

		/* 출구에 도달하면 정상 종료 */
		else if (a->row == 7 && a->col == 14)
		{
			finalstep(maze, a);
			return 1;
		}

		/* 동서남북에 길이 있는지 검사 */
		else if ((d = dir_check(maze, a)) < 4)
		{	
			int row = a->row, col = a->col;
			footstep(maze, a);
			if (d == 0)			// 북
				row -= 1;
			else if (d == 1)	// 동
				col += 2;
			else if (d == 2)	// 남
				row += 1;
			else if (d == 3)	// 서
				col -= 2;
			if ((a = push(way, &w, row, col)) == NULL)  // 신규 좌표 생성
				return 0;
		}

		/* 갈 길이 더 이상 없을 경우 */
		else
		{
			backstep(maze, a);
			pop(way, &w);
			a = way[w - 1];
			// w는 항상 새로 쓸 위치에 가 있기 때문에 마지막 위치는 w-1
		}
		maze_print(maze);
	}
	return 1;
}

 

---

 

[ location* push(), location* new_location() - 신규 좌표 생성 ]

• 다음 좌표값의 좌표를 던져주면 신규 구조체 생성해서 주소 반환
• 위치값을 사용할때는 모든 함수에서 현재 위치가 동일한 위치를 가리키도록 해야 안헷갈림 (w는 항상 새로 쓸 위치를 가리키고 있으므로 실제 마지막 저장값은 w-1에 위치하도록 함)
• MAX값 이상이 될 수 없으므로 realloc은 하지 않음

/* 스택(배열)에 추가 */
/* parameter : 위치저장 스택, 저장갯수 포인터, 신규 저장할 row, col*/
/* return : 정상 == 신규 생성된 주소, 비정상 == NULL */
location* push(location* way[], int* w, int row, int col)
{
	if ((way[*w] = new_location(w)) == NULL)
		return NULL;
	way[*w]->row = row;
	way[(*w)++]->col = col;
	
	return way[(*w) - 1];
}


/* 위치 저장 공간 생성 */
/* parameter : void */
/* return : 정상 == 신규 공간 주소, 비정상 == NULL */
location* new_location(int* w)
{
	/* max에 도달한 경우 NULL값 반환 */
	if (*w == MAX)
	{
		puts("길을 찾지 못했습니다.");
		return NULL;
	}
	location* temp;
	if ((temp = (location*)malloc(sizeof(location))) == NULL)
	{
		puts("메모리가 부족합니다.");
		exit(1);
	}
	/* 초기화 */
	temp->row = 0;
	temp->col = 0;
	
	return temp;
}

 

---

 

[ pop() - 지나온 길을 되돌아갈 때 스택(배열)의 이전 값으로 돌려줌 ]

• 기능 상 굳이 없앤 값을 NULL처리할 필요는 없지만 NULL처리 해주는게 디버깅할 때 편리함

/* 스택(배열)에서 하나 제거 */
/* parameter : 위치저장 스택, 저장갯수 포인터*/
/* return : void */
void pop(location* way[], int* w)
{
	/* 신규 시작점까지 없어진 상황이라면 */
	if (*w == 0)
	{
		puts("길이 이상합니다..");
		exit(1);
	}
	/* w는 항상 새로 쓸 위치에 자리하고 있기 때문에, 마지막 값은 w - 1 */
	free(way[*w-1]);
	way[(*w)-- - 1] = NULL;
}

 

---

 

 

[ int iswhat() - 다음 이동할 좌표의 값이 길(□)인지 확인 ]

• 특수문자(특수기호)의 실제 저장 값 확인은 특수문자를 문자열에 넣은 뒤 디버깅해서 확인했음
• 윈도우즈 또는 비주얼 스튜디오 외에서는 제대로 작동하지 않을 수 있을 것 같음
• 간단히 구글링을 해봤으나 저 숫자가 정확히 의미하는 바는 아직 잘 모르겠음 (아스키코드는 아니고 유니코드도 아닌 것 같음)

/* 이동할 위치의 유형 확인하기 */
/* parameter : 미로배열, 확인할 위치값(row, col) */
/* return : 길 == □(1), 그 외 == 0 */
int iswhat(char maze[][COL], int row, int col)
{
	if (maze[row][col] == -95 &&
		maze[row][col + 1] == -32)
		return 1;
	return 0;
}

 

---

 

[ int dir_check() - 동서남북 방향에 길이 있는지 확인 ]

 

/* 동서남북에 길이 있는지 확인 */
/* parameter : 미로배열, 확인할 위치값(a) */
/* return : 북(0), 동(1), 남(2), 서(3) */
int dir_check(char maze[][COL], location* a)
{
	/* [북쪽확인] 위에 행이 있고 갈 수 있는 길일 때 '□' */
	if (a->row > 0 && iswhat(maze, a->row - 1, a->col) == 1)
		return 0;

	/* [동쪽확인] 오른쪽에 열이 있고 갈 수 있는 길일 때 */
	/* 2byte 문자구성이라, 좌우 이동은 2칸씩 이동해야함 */
	else if (a->col + 2 < COL && iswhat(maze, a->row, a->col + 2) == 1)
		return 1;

	/* [남쪽확인] 아랫쪽에 행이 있고 갈 수 있는 길일 때 */
	else if (a->row + 1 < ROW && iswhat(maze, a->row + 1, a->col) == 1)
		return 2;

	/* [서쪽확인] 아랫쪽에 행이 있고 갈 수 있는 길일 때 */
	else if (a->col > 0 && iswhat(maze, a->row, a->col - 1) == 1)
		return 3;
	/* 그 외 */
	return 4;
}

 

---

 

[ void footstep(), void backstep(), void finalstep() - 해당 좌표에 기호 넣어주기 ]

• 1byte 문자면 함수없이 썼을텐데 멀티바이트 문자라 두줄이 돼서 따로 빼줌

※ Point
잘려고 누우니까 문득, 그냥 숫자로 미로를 그려두고 출력만 문자로 대신 해주면 안되나 싶어 해보니 잘 됨... 그럼 복잡하게 이런식으로 하지 않아도 됨 (난 바보야..)
ex) if (a[i] == 0) printf("⊙")
ex) switch (a[i]) case 0: printf("⊙"); break; 등으로 대체 가능

/* 지나간 자리 표시 넣어주기 (⊙) */
/* parameter : 미로배열, 현재 위치 좌표 */
/* return : void */
void footstep(char maze[][COL], location* a)
{
	maze[a->row][a->col] = -94;
	maze[a->row][a->col + 1] = -63;
}


/* 돌아간 자리 표시 넣어주기 (▣) */
/* parameter : 미로배열, 현재 위치 좌표 */
/* return : void */
void backstep(char maze[][COL], location* a)
{
	maze[a->row][a->col] = -94;
	maze[a->row][a->col + 1] = -61;
}


/* 출구 자리 표시 넣어주기 (↘) */
/* parameter : 미로배열, 현재 위치 좌표 */
/* return : void */
void finalstep(char maze[][COL], location* a)
{
	maze[a->row][a->col] = -94;
	maze[a->row][a->col + 1] = -39;
}

 

---

 

[ void maze_print() - 미로 출력 ]

• main() 함수에 썼다가 한칸 이동할 때마다 출력하기 위해 따로 함수로 빼둠
• 혹시 애니메이션같이 시간차로 출력할 수 있는 방법을 찾으면 사용하면 됨

void maze_print(char maze[][COL])
{
	printf("\n\n");
	for (int i = 0; i < ROW; ++i)
		printf("\t%s\n", &maze[i][0]);
}

 

---

 

콘솔창에 출력 내용을 지우고 (cls 명령어같이) 시간차로 출력해주는 기능이 있을것도 같은데.. 내일 한 번 찾아보도록 하겠습니다. ㅎㅎ