스택 - 미로찾기 프로그램

10060 단어 자료구조자료구조

알아야 할 것!

스택

후입선출(LIFO:Last-In First-Out)
가장 최근에 들어온 데이터가 가장 먼저 나감

이를 이용해 미로찾기 알고리즘을 작성할 수 있다!

더블 버퍼링

미로를 출력하는 기존 방식이다.

system("cls") 으로 cmd를 통째로 지웠다가 다시 cmd에 미로를 출력하는 기존 방식이다. 200ms마다 cmd를 지웠다가 미로를 출력하는 명령을 반복하는데, 깜빡임이 심한 걸 볼 수 있다. 10ms 정도로 빠른 속도로 이를 반복하면... 대참사..! 정신나간 나이트클럽..!

구글링해본 결과 '더블 버퍼링' 으로 이를 해결할 수 있다고 한다. 다른 블로그나 유튜브를 참조하여 8시간동안 삽질해서 해결했다!

더블 버퍼링의 원리는 화면1과 화면2를 만들고, 이를 비교해서 다른 부분만 바꿔주는 원리이다. 기본적으로 화면 1을 출력하고, 화면2에는 미로를 업데이트한다. 화면1과 화면2를 비교 후 미로의 바뀐 부분만 해당 좌표로 가서 그 부분만 수정한다.

미로찾기 프로그램

Visual Studio 프로젝트 속성의 명령인수에 <input.txt 를 입력한다.

전체 코드 :

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <windows.h>
#include <time.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100
#define MAZE_SIZE_Y 32
#define MAZE_SIZE_X 52

char maze[MAZE_SIZE_Y][MAZE_SIZE_X];




// cmd의 화면 커서 안보이게 하는 코드
void CursorView()
{
	CONSOLE_CURSOR_INFO cursorInfo = { 0, };
	cursorInfo.dwSize = 1; //커서 굵기 (1 ~ 100)
	cursorInfo.bVisible = FALSE; //커서 Visible TRUE(보임) FALSE(숨김)
	SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursorInfo);
}


// cmd에 미로를 출력할 때 cmd에 출력된 문자들을 초기화하는 window("cls") 사용 시 화면 깜빡임 발생
// 아래 코드들은 system("cls") 대신 '화면1'(백버퍼), '화면2'(프론트버퍼) 를 만들어서 cmd에 출력하는 코드
// 화면1(백버퍼)와 화면2(프론트버퍼) 를 비교 후 바뀐 부분만 다시 렌더링하는 과정을 거친다.
// 아래 작성한 코드는 '더블 버퍼링' 이라고 부른다. (feat. 구글링)

/*[더블 버퍼링 구현 코드 시작]*/
	char front_buffer[MAZE_SIZE_Y][MAZE_SIZE_X];
	char back_buffer[MAZE_SIZE_Y][MAZE_SIZE_X];

	void initializeBuffer() { // 백버퍼(화면1), 프론트버퍼(화면2) 초기화
		for (int y = 0; y < MAZE_SIZE_Y; y++) {
			for (int x = 0; x < MAZE_SIZE_X; x++) {
				front_buffer[y][x] = '\0';
				back_buffer[y][x] = '\0';
			}
		}
	}
	void drawToBackBuffer() { // 백버퍼에 미로를 그려 넣는다
		for (int y = 0; y < MAZE_SIZE_Y; y++) {
			for (int x = 0; x < MAZE_SIZE_X; x++) {
				back_buffer[y][x] = maze[y][x];
			}
		}
	}
	void gotoxy(int x, int y) // cmd 출력위치 변경
	{
		COORD Cur;
		Cur.X = x;
		Cur.Y = y;
		SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), Cur);
	}
	void render() {
		for (int y = 0; y < MAZE_SIZE_Y; y++) {
			for (int x = 0; x < MAZE_SIZE_X-1; x++) {
				if (back_buffer[y][x] != front_buffer[y][x]) { // 백버퍼(화면1) 프론트버퍼(화면2) 가 다르면
					gotoxy(x * 2, y); // 해당 위치로 이동 후 cmd에 출력
					switch (back_buffer[y][x]) {
					case '0':printf("  "); break;
					case '1':printf("■"); break;
					case '2':printf("○"); break;
					case 'e':printf("→"); break;
					case 'x':printf("¶"); break;
					}
				}
			}
		}
		// 프론트버퍼(화면2)를 현재 백버퍼(화면1)로 업데이트
		for (int y = 0; y < MAZE_SIZE_Y; y++) {
			for (int x = 0; x < MAZE_SIZE_X; x++) {
				front_buffer[y][x] = back_buffer[y][x];
			}
		}
	}
/*[더블 버퍼링 구현 코드 끝]*/



// AI 미로찾기 시작 전 출력하는 함수
void printBeforeStart(int AI_speedINT, int startCountINT) {
	int CNT = startCountINT / 1000;
	while (startCountINT/1000) {
		printf("------------------------------------------------------------------\n\n");
		printf(" [ 미로찾기! - 자료구조 스택을 이용해서 미로 경로 찾기 ] \n\n");
		printf(" input.txt 에서 AI의 속도, 시작 전 카운트 값,\n 미로 구조를 변경 및 설정할 수 있습니다.\n\n");
		printf(" AI 속도 : %dms \n\n %d초 후 시작!     %d \n\n", AI_speedINT, startCountINT / 1000, CNT--);
		printf("------------------------------------------------------------------\n\n");
		
		printf("input.txt 에 저장되어 있는 미로 : \n");
		for (int i = 0; i < 31; i++) {
			for (int j = 0; j < 51; j++) {
				switch (maze[i][j]) {
				case '0':printf("  "); break;
				case '1':printf("■"); break;
				case '2':printf("○"); break;
				case 'e':printf("→"); break;
				case 'x':printf("¶"); break;
				}
			}
			printf("\n");
		}
		Sleep(1000);
		if (CNT<0) break;
		system("cls");
	}
}


typedef struct {
	short r;
	short c;
} element;

element here = { 1,0 }, entry = { 1,0 };

typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

// 스택 초기화 함수
void init_stack(StackType* s) {
	s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType* s) {
	return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType* s) {
	return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}

void push_loc(StackType* s, int r, int c) {
	if (r < 0 || c < 0) return;
	if (maze[r][c] != '1' && maze[r][c] != '2') {
		element tmp;
		tmp.r = r;
		tmp.c = c;
		push(s, tmp);
	}
}

// 기존 maze_print 함수는 render() 함수로 대체
//
//void maze_print(char maze[MAZE_SIZE_Y][MAZE_SIZE_X]) {
//	printf("\n");
//	for (int i = 0; i < 31; i++) {
//		for (int j = 0; j < 51; j++) {
//			switch (maze[i][j]) {
//			case '0':printf("  "); break;
//			case '1':printf("■"); break;
//			case '2':printf("○"); break;
//			case 'e':printf("→"); break;
//			case 'x':printf("¶"); break;
//			}
//		}
//		printf("\n");
//	}
//	Sleep(200);
//	system("cls");
//}

int main() {
	
	char AI_speed[100]; // input.txt 에서 받아들일 문자열
	char startCount[100]; // input.txt 에서 받아들일 문자열

	int AI_speedINT = 0; // AI speed 초깃값
	int startCountINT = 0; // startCount 초깃값

	// input.txt의 AI_speed 를 읽어들임
	for (int i = 0; i < 100; i++) {
		scanf("%c", &AI_speed[i]);
		if (AI_speed[i] == '\n') break;
	}
	// AI_speed='숫자' 에서 char형인 숫자를 int형으로 변경 후 AI_speedINT 에 저장
	for (int i = 13; i < 100; i++) {
		if (AI_speed[i] == '\n') break;
		AI_speedINT *= 10;
		AI_speedINT += AI_speed[i] - '0';
	}
	// input.txt의 startCount 를 읽어들임
	for (int i = 0; i < 100; i++) {
		scanf("%c", &startCount[i]);
		if (startCount[i] == '\n') break;
	}
	// startCount='숫자' 에서 char형인 숫자를 int형으로 변경 후 startCountINT 에 저장
	for (int i = 11; i < 100; i++) {
		if (startCount[i] == '\n') break;
		startCountINT *= 10;
		startCountINT += startCount[i] - '0';
	}

	// input.txt 의 미로를 읽어들임
	for (int i = 0; i < 32; i++) {
		for (int j = 0; j < 52; j++) {
			scanf("%c", &maze[i][j]);
		}
	}

	// 더블 버퍼링 - 버퍼 초기화 및 백버퍼(화면1) 를 input.txt 에 있는 maze 로 초기화
	initializeBuffer();
	drawToBackBuffer();


	// cmd 창 크기
	system("mode con cols=150 lines=47");

	// cmd 커서 안보이게 하기
	CursorView();

	// input.txt에 있는 AI_speedINT와 startCountINT 의 값과 기타 인터페이스를 시작 전에 출력
	printBeforeStart(AI_speedINT, startCountINT);

	system("cls");
	Sleep(1000);

	int r, c;
	StackType s;
	init_stack(&s);
	here = entry;
	while (maze[here.r][here.c] != 'x') {
		r = here.r;
		c = here.c;
		maze[r][c] = '2';
		// maze_print(maze); 대신
		// render(); 와 drawToBackBuffer(); 이용
		render();
		drawToBackBuffer(); // 백버퍼(화면1) 업데이트
		Sleep(AI_speedINT);
		push_loc(&s, r - 1, c);
		push_loc(&s, r + 1, c);
		push_loc(&s, r, c - 1);
		push_loc(&s, r, c + 1);
		if (is_empty(&s)) {
			gotoxy(0, MAZE_SIZE_Y + 4);
			printf("실패\n");
			return 0;
		}
		else
			here = pop(&s);
	}
	printf("성공! ");
	gotoxy(0, MAZE_SIZE_Y + 4);
	return 0;
}

input.txt :

AI_speed(ms)=3
startCount=10000
111111111111111111111111111111111111111111111111111
e00000001000000010100000000000001000000000001000001
101011111010111010101111111011111010111111101110111
101010001010101010101000001000000010001000100010001
111010101010101010101110101111111111101010111011101
100010100010100000100000100010000000100010001000001
101110111110111110111111111010111011111011101111111
101000100010001000000000100010100010001000100000001
101011101011101111111111101111101010101110111111101
101000101000100000000010001000001010101010100000101
101110101110111111111010111011111110101010101110101
100010100010100000001010100000001000101000100010101
101010111010111011101010111111101011101011111010101
101010100010000010101000100000001010101000000010101
101110101111111110101111101111101010101111111111101
100000100010000000001000001000001010001000000000101
101111111011101111111011111011111010111011111110101
101000001000100010000010100010001010000010100010101
101011101110111010111110101111101010111110101110101
101010101000101000101000001000001010100010101000101
101010101011101111101011111011101011101010101011101
100010101000101000001010000000101000101010101010001
111110101110101011101011111110101110101010101010111
100010001000100010001000000000101010001000100010001
101110111011101110101111111111101011111111101110101
100000100010101000100000100000001000100000101000101
101111111010101011111110101111111110101110101111101
100010001010101010000000101000100010100010001000001
111010101010101011111111101010101010111011111011101
10000010001000100000000000001000100000100000001000x
111111111111111111111111111111111111111111111111111

결과

input.txt에 쓰여진 대로 프로그램이 잘 돌아간다.

만약 input.txt에 미로 출구 부분인 x를 없애면 더 이상 경로를 탐색할 수 없기 때문에 '실패'를 출력한다.

느낀점 :

미로찾기 프로그램을 작성하는 데에 '스택'이라는 자료구조를 활용해 만들었다. 다른곳에도 스택이 쓰일 수 있는지 궁금해졌다. 또한 프로그램을 만들면서 '더블 버퍼링'이라는 것도 알게 되었다. 삽질한 보람이 있다!

github : Forking Workflow
멋쟁이 사자처럼 FE 2기 - 3

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage