큐 구조_미로찾기 (최종 ver) [3/3]

만들다보니 갑자기 욕심이 생겨서 조금 더 기능을 추가하게 됐습니다. 중요한거만 얼른 하고 넘어가야 하는데 계속 딴길로 새서 문제네요.. 최단 거리를 찾기 위해 고민하다가 결국 모든 길을 다 돌아다녀봐야한다는 점에 착안해서 만들어봤습니다. 동서남북방향을 동시에 다 가보고 제일 먼저 도착하는 길을 찾는 방식입니다.

​

이전 버전을 만들고 나서 좀 미흡해보였던 부분들을 수정하고, 추가로 필요한 기능들을 넣어서 다시 만들어 보았습니다.

 

 

• 분기점이 나올 때마다 새로운 길이 생김
• 몇 개의 길이 발생할지 모르니 일반 배열을 사용하기가 어려움. 연결리스트 사용
• 왔던 길을 되돌아가는 구조가 아니라서 스택구조와는 크게 관계가 없는 자료구조가 됨
• 아래와 같이, 출발점을 기준으로 갈 수 있는 길이 나오면 다시 그 길을 기준으로 길을 찾음
• 새로운 길들은 이전 길의 좌표를 가지고 있어 역순의 연결리스트가 됨
• 새로 찾은 길들을 저장한 후, 기준 길 정보를 지워줘야 하기 때문에 스택구조와는 반대가 됨 (선입선출)

 

간이 더블 버퍼링을 통해 깜박임 문제를 없애는 방식은 아래 글에 자세히 나와 있습니다.

2019/12/05 - [C언어/개발 TIP] - 콘솔 깜박임 없애는 방법 (쉬운 더블 버퍼링)

 

※ Point
강의를 듣다보니 이게 큐(Queue) 구조를 활용한 예시로 나오네요.
- 스택 구조 : 후입선출 (나중에 들어온게 먼저 나감)
- 큐 구조 : 선입선출 (먼저 들어온게 먼저 나감)
위와 같이 이해하면 되고, 그냥 하다가 필요하면 그 때 그 때 응용해서 사용하면 될 것 같습니다.

 

---

 

[ main() ]

• 콘솔창 크기 조정, 커서(cursor) 숨기기 기능 추가
• 이전 버전과 다르게 미로는 숫자로 구성하여, char 타입의 배열로 만듦
• 콘솔 창 또한 매크로로 숫자를 정의해 쉽게 바꿀 수 있도록 함

※ Point
- 콘솔창 크기 조절은 system("")명령어를 사용하면 됨
- 매크로 사용을 위해 String으로 명령어를 만들어 삽입

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#define SIZE 15
#define CONSOLE_WIDTH 80
#define CONSOLE_HEIGHT 40

typedef struct l location;
typedef struct f find;

/* 좌표 저장 */
struct l {
	int row;  // 상하
	int col;  // 좌우
	location* pre;  // 이전 길 위치
};

/* 검색 기준점 */
struct f {
	location* loc;	// 검색할 기준 위치 (좌표)
	find* next;	// 다음 검색할 기준 위치 (좌표)
};

int make_maze(char maze[][SIZE], char* read_file);
void maze_print(int j, int i, char c);
int maze_runner(char maze[][SIZE]);
location* create_location(int row, int col, location* a);
find* create_find(location* a);
void remove_find(find** head);
int dir_checker(char maze[][SIZE], int row, int col);
int all_around_checker(char maze[][SIZE], location* a, find** tail);
void final_step(char maze[][SIZE], find* tail);
void gotoxy(int x, int y);
void buffer_print(char maze[][SIZE]);
void CursorView(char hide);

void main()
{
	/* 콘솔 창 크기 조절 및 커서 숨기기 */
	char console_size[30];
	sprintf_s(console_size, 30, "mode con cols=%d lines=%d",
		CONSOLE_WIDTH, CONSOLE_HEIGHT);
	system(console_size);
	CursorView(0);

	/*미로 그림 만들기(파일에서 가져오기) */
	char maze[SIZE][SIZE] = { 0 };
	make_maze(maze, "maze.txt");
	maze_runner(maze);
}

 

---

 

[ int make_maze() = 텍스트 파일에서 읽어와 미로 배열 만들기 ]

• 숫자로 만들기 어렵기 때문에 엑셀에서 만든 후, 텍스트 파일로 옮겨옴
• 엑셀 표 → 텍스트파일 복사 시, 글자 사이에 tab이 생겨 없애줌
• fopen() 함수와 달리, fopen_s() 함수의 경우 errno_t 타입의 변수에 담아줘야 함
• (파일 읽기에 실패할 경우, 해당 변수에 에러 타입이 저장됨)

/* 미로 만들기(파일에서 가져오기) */
/* parameter : 미로배열, 파일 이름 */
/* return : 정상 == 1, 비정상 == 0 */
int make_maze(char maze[][SIZE], char* read_file)
{
	FILE* read = NULL;
	errno_t err;
	err = fopen_s(&read, read_file, "r");
	if (read == NULL)
		return 0;

	/* 파일에서 읽어서 tab 없애서 배열에 넣어줌 */
	char c;
	int i = 0;
	int j = 0;
	while ((c = fgetc(read)) != EOF)
	{
		if (c != '\t' && c != '\n' && j < SIZE)
			maze[i][j++] = c;
		else if (c == '\n' && i < SIZE)
		{
			i++;
			j = 0;
		}
	}
	fclose(read);
	return 1;
}

 

---

 

[ location* create_location() - location 구조체 1개 생성 ]

• 신규 좌표 생성 시, 기존 기준점 좌표의 정보를 가지고 있는 역순의 연결리스트로 구성함

/* 신규 location 1개 생성 */
/* parameter : low, col 좌표값, 현재 좌표 */
/* return : 신규 생성된 구조체 주소 */
location* create_location(int row, int col, location* a)
{
	location* temp = (location*)malloc(sizeof(location));
	if (temp == NULL)
		return NULL;
	temp->row = row;
	temp->col = col;
	temp->pre = a;
	return temp;
}

 

---

 

[ find* create_find() - find 구조체 1개 생성 ]

• 새로 생성된 좌표를 가리키는 별도의 연결리스트 구조체 생성
• 새로 생성된 좌표 하나하나가 다음 번 새로운 길을 찾을 기준점 좌표가 되기 때문에 별도 저장
• 이번 미로 찾기에서 가장 중요한 로직이라고 할 수 있음

/* 신규 find 1개 생성 */
/* parameter : location* a */
/* return : 신규 생성된 구조체 주소 */
find* create_find(location* a)
{
	find* temp = (find*)malloc(sizeof(find));
	if (temp == NULL)
		return NULL;
	temp->loc = a;
	temp->next = NULL;
	return temp;
}

 

---

 

[ void remove_find() - 검색을 완료한 기존 좌표 정보를 지워줌 ]

• find 연결리스트의 가장 앞(head)을 지워줌
• 기준좌표의 동서남북을 검색해 새로운 좌표를 모두 찾았다면, 기준좌표를 지워줌

※ Point (함수의 parameter가 포인터변수일 때 주의사항)
- 포인터변수가 가리키는 값을 변경할 때는 포인터 변수를 드대로 parameter로 받으면 됨
- 하지만 포인터 변수 자체를 바꿔주기 위해서는 더블 포인터로 parameter를 받아줘야 함
- 즉, 함수의 parameter와 argument는 서로 다른 변수로, 값만 복사해서 가져오는점에 유의

 

/* find 연결리스트의 가장 앞의 값(head) 삭제 */
/* parameter : find 시작 값 head의 주소 */
/* return : void */
void remove_find(find** head)
{
	find* temp = (*head)->next;
	free(*head);
	*head = temp;
}

 

---

 

[ int all_around_checker ]

• 현재 좌표를 기준으로 동서남북 확인 후, 길이 있으면 해당 좌표를 연결리스트로 생성
• find 연결리스트의 경우 계속 뒤에 추가가 되어야하므로 마지막 위치를 항상 기억하고 있도록 함
• 출구에 도달했을 경우 -1을 리턴하여 마지막 작업을 수행함
• char 타입의 문자열 배열이므로, 숫자는 아스키코드로 저장됨 ( 0 == 48)

/* argument로 제공된 현재 좌표의 동서남북 길 확인 후 좌표 생성 */
/* parameter : 현재좌표, find의 마지막 값(tail)의 주소 */
/* return : 새로운 길의 좌표를 생성한 갯수, 종료지점 도달 시 == -1*/
int all_around_checker(char maze[][SIZE], location* a, find** tail)
{
	/* 현재 좌표 기준 동서남북 좌표 생성 */
	int dir[4][2] = { {a->row, a->col + 1}, {a->row, a->col - 1},
		{a->row + 1, a->col}, {a->row - 1, a->col} };
	int count = 0; // 길이 있어서 실제 좌표를 생성한 횟수

	/* 현재 좌표 기준 동서남북 길 확인 */
	for (int i = 0; i < 4; ++i)
	{
		location* temp_location;
		find* temp_find;

		/* 해당 방향이 미로의 마지막 지점이라면 체크하지 않음 */
		if (i == 0 && a->col == SIZE - 1)
			continue;
		else if (i == 1 && a->col == 0)
			continue;
		else if (i == 2 && a->row == SIZE - 1)
			continue;
		else if (i == 3 && a->row == 0)
			continue;

		/* 해당 방향이 길이라면 */
		if (dir_checker(maze, dir[i][0], dir[i][1]) == 0)
		{
			temp_location = create_location(dir[i][0], dir[i][1], a);
			// 신규 좌표점 생성
			temp_find = create_find(temp_location);  // find 포인터 생성
			(*tail)->next = temp_find;  // 기존 연결리스트에 붙여줌
			*tail = temp_find;  // tail값도 바꿔줌
			count++;  // 생성된 좌표 카운트

			/* 지나간 길 표시 (출구일경우 다르게) */
			if (dir[i][0] == SIZE - 1 && dir[i][1] == SIZE - 1)
			{
				maze[dir[i][0]][dir[i][1]] = 52;
				return -1;
			}
			maze[dir[i][0]][dir[i][1]] = 50;
		}
	}
	return count;
}

 

---

 

[ void final_step() - 출구를 찾았을 때 최단경로 표시 ]

• 마지막 좌표부터 역순의 연결리스트이므로, 역순으로 찾아들어가며 값을 변경해줌

/* 출구를 찾으면 최단거리 길을 표시해줌 */
/* parameter : 미로배열, tail */
/* return : void */
void final_step(char maze[][SIZE], find* tail)
{
	location* p;
	p = tail->loc;
	// 마지막 출구는 ↘로 남아있도록 제일 마지막 전점부터 시작함
	// 출발지도 그대로 남아있도록 제일 처음 이후점에서 끝냄
	while (p->pre->pre != NULL)
	{
		p = p->pre;
		maze[p->row][p->col] = 53;
		buffer_print(maze);
		Sleep(100);
	}
}

 

---

 

[ void gotoxy() - 커서위치(출력 좌표) 변경 ]

• windows.h 삽입 필요
• 윈도우 API 함수를 모두 이해할 것이 아니라면 적당히 인터넷에서 가져다 사용하면 됨

/* 콘솔 출력 좌표 설정 */
/* parameter : x축, y축 */
/* return : void */
void gotoxy(int x, int y)
{
	COORD pos = { x,y };
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
}

 

---

 

[ void CursorView() - 커서 숨기기 ]

• 콘솔 출력 시 깜박거리는 커서를 숨겨주는 함수
• 게임을 만들거나 애니메이션을 만들 때는 숨겨주는게 깔끔함
• gotoxy() 함수 사용 시 커서를 숨겨주지 않으면 커서 위치가 여기저기 옮겨다니면서 깜박임

/* 커서 숨기기 */
/* parameter : 숨기기 : 0, 보이기 : 1*/
/* return : void */
void CursorView(char hide)
{
	HANDLE hConsole;
	CONSOLE_CURSOR_INFO ConsoleCursor;

	hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
	ConsoleCursor.bVisible = hide;
	ConsoleCursor.dwSize = 1;

	SetConsoleCursorInfo(hConsole, &ConsoleCursor);
}

 

---

 

[ void buffer_print() - 애니메이션 출력 시 깜박임을 없애기 위한 더블버퍼링 ]

• 이전 버전과 달리, 미로 size를 키우니 gotoxy() 함수로 덮어쓰는 출력으로도 깜박임 발생
• 인터넷에 나오는 윈도우 API 함수를 활용한 더블 버퍼링은 너무 과해보였음
• 궁여지책 끝에 배열을 하나 더 만들어서 바뀐 부분만 출력하는 방식으로 깜박임을 없앰
• 출력은 2byte짜리 특수문자이므로 가로축의 좌표는 2씩 증가시켜야 함
• 자세한 내용은 아래 링크 참조

/* 버퍼로 받아서 출력 */
/* parameter : 미로배열 */
/* return : void */
void buffer_print(char maze[][SIZE])
{
	static char front_buffer[SIZE][SIZE] = { ' ' };

	/* 현재 미로와 front_buffer(이전 미로)에 있는 미로 비교 */
	for (int i = 0; i < SIZE; ++i)
		for (int j = 0, j2 = 0; j < SIZE; ++j)
		{
			if (front_buffer[i][j] != maze[i][j])
			{
				maze_print(j2, i, maze[i][j]);
				// 바뀐 부분 화면에 출력
				front_buffer[i][j] = maze[i][j];
				// 바뀐 부분은 출력 후 front_buffer에 저장
			}
			j2 += 2;
		}
}

 

---

 

[ void maze_print() - 주어진 좌표에 해당 문자 출력 ]

• 배열의 좌표를 주면 해당 좌표에 특수기호 출력
• gotoxy() 함수의 좌표는 배열과 반대인 점에 유의(arr[세로축][가로축] == gotoxy(가로축, 세로축))
• '★' 출력 시 윈도우 API 함수를 통해 색상을 변경함
• 커서위치를 항상 영향 범위 밖으로 두도록 마무리 시켜야 깔끔하게 처리됨

※ Point (콘솔 글자 색상 변경)
- windows.h 헤더 삽입
- SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 색상번호)
- 함수 적용 후 출력되는 글자는 계속 해당 색상 유지
- 바꿔가면서 출력하려면 계속 함수를 적용해 바꿔줘야 함
(노란색으로 바꿔 출력하고 다시 까만색으로 바꿔주면 특정글자만 노란색으로 바꿔 출력 가능)

/* 한글자 출력 */
/* prarameter : 좌표 값, 바꿀 문자 */
/* return : void */
void maze_print(int j, int i, char c)
{
	gotoxy(10 + j, 5 + i);	// 가운데 출력을 위해 상수를 더해줌
	switch (c)
	{
	case 48:
		printf("□");
		break;
	case 49:
		printf("■");
		break;
	case 50:
		printf("⊙");
		break;
	case 51:
		printf("▩");
		break;
	case 52:
		printf("↘");
		break;
	case 53:
		SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 6);
		printf("★");
		break;
	}
	gotoxy(10 + SIZE, 5 + SIZE); // 출력 후 커서 대기 위치
}

 

---

 

이렇게 미로 찾기도 끝!