[C++로 쉽게 풀어쓴 자료구조] 미로 탐색 프로그램 ( 스택, 큐, 덱)

안녕하세요 여니입니다

오늘은 스택과 큐 덱을 이용한 미로탐색  프로그램에 대해 알아보는 시간을 가지려 합니다

(출처는 C++로 쉽게 풀어쓴 자료구조 책이구요!)

1. 스택을 이용한 미로 탐색 프로그램

 

일단 위에 있는 사진 보이시나요?

스택을 이용한 미로탐색 프로그램을 실행시킨 결과값인데요!

 

미로사이즈를 6X6으로 정하고 시작했습니다

 

 

 

 

 

 

일단 현재 위치를 나타내기 위해서 Location2D라는 헤더파일을 하나 작성해줍니다

<Location2D>

struct Location2D {
	int row; // 현재 위치의 행 번호
	int col; // 현재 위치의 열 번호
	Location2D(int r = 0, int c = 0) { row = r; col = c; }
	bool isNeighbor(Location2D& p) { // 위치 p가 자신의 이웃인지 검사하는 함수
		return (row == p.row && (col == p.col - 1 || col == p.col + 1)) || (col == p.col && (row == p.row - 1 || row == p.row + 1));
		//true를 반환하면 이웃
		// false를 반환하면 이웃이 아니다
	}
	//연산자 오버로딩을 사용해서 위치p가 자신과 같은 위치인지를 검사하는 함수이다.
	bool operator==(Location2D& p) { return row == p.row && col == p.col; }
};

 

현재 위치를 위해서 구조체 Location2D를 정의했습니다

Location2D 생성자를 선언해서 현재위치를 초기화해 주고, isNeighbor이라는 bool형 함수를 이용해서 위치p가 현재위치와 이웃인지 검사를 하는데 이웃일 경우에는 true, 이웃이 아니면 false를 반환합니다.

 

연산자 오버로딩을 사용해서 위치p가 현재 자신과 같은 위치인지를 검사하는 함수인데 같은 위치라면 true 반환!

 

 

이번엔 스택미로.cpp에 대해 알아보도록 하죠

<스택미로.cpp>

#include "Location2D.h"
#include <stack>

using namespace std;
const int MAZE_SIZE = 6;
char map[MAZE_SIZE][MAZE_SIZE] = {
	//맵 , e는 자기자신, 1은 벽, 0은 길, x는 먹이
	{'1','1','1','1','1','1'},
{'e','0','1','0','0','1'},
{'1','0','0','0','1','1'},
{'1','0','1','0','1','1'},
{'1','0','1','0','0','x'},
{'1','1','1','1','1','1'},
};
//(r,c)가 갈 수 있는 위치인지 검사하는 함수이다
bool isValidLoc(int r, int c) {
	//만약 r,c가 0보다 작거나 MAZE_SIZE보다 값이 크면 FASLE 반환
	if (r < 0 || c < 0 || r >= MAZE_SIZE || c >= MAZE_SIZE) {
		return false;
	}
	else
		//아니라면 '0' 또는 'X일경우 true 반환
		return map[r][c] == '0' || map[r][c] == 'x';
}
void main() {
	stack<Location2D> locStack; //STL
	Location2D entry(1, 0); //e 위치
	locStack.push(entry); //스택에 entry위치값 push

	while (locStack.empty() == false) {
		Location2D here = locStack.top(); //복사
		locStack.pop(); // 삭제

		int r = here.row;
		int c = here.col;
		printf("(%d,%d)", r, c);
		if (map[r][c] == 'x') { //현재 위치가 출구라면? 
			printf("미로탐색 성공\n");
			return;
		}
		else { // 현재 위치가 출구가 아니라면?
			map[r][c] = '.';
			if (isValidLoc(r - 1, c))locStack.push(Location2D(r - 1, c));
			if (isValidLoc(r + 1, c))locStack.push(Location2D(r + 1, c));

			if (isValidLoc(r, c - 1))locStack.push(Location2D(r , c - 1));
			if (isValidLoc(r, c + 1))locStack.push(Location2D(r , c + 1));



		}
	}
	printf("미로탐색 실패\n");


}

STL의 스택을 이용한 미로탐색!

stack<Location2D> locStack; // 위치 스택 객체를 생성한다.
Location2D entry(1, 0); // 입구 객체를 생성하고 초기화한다. 
locStack.push(entry); // 스택에 entry 위치값 push

 

 

 

 

 

 

2. 큐를 이용한 미로 탐색 프로그램

이번엔 큐를 이용해서 미로탐색 프로그램을 한번 구현해보도록 할게요(너비 우선 탐색)

Location2D는 맨위에 나와있는 Location2D와 내용이 동일하니까 생략할게요!

 

<큐미로.cpp>

#include "Location2D.h"
#include <queue>
using namespace std;
const int MAZE_SIZE = 6;
char map[MAZE_SIZE][MAZE_SIZE] = {
		{'1','1','1','1','1','1'},
{'e','0','1','0','0','1'},
{'1','0','0','0','1','1'},
{'1','0','1','0','1','1'},
{'1','0','1','0','0','x'},
{'1','1','1','1','1','1'},
};
bool isValidloc(int r, int c) {
	if (r < 0 || c < 0 || r >= MAZE_SIZE || c >= MAZE_SIZE) {
		return false;
	}
	else {
		return map[r][c] == '0' || map[r][c] == 'x';
	}

}
void main() {
	queue<Location2D>locQueue;
	Location2D entry(1, 0);
	locQueue.push(entry);

	while(locQueue.empty() == false) {
		Location2D here = locQueue.front();
		locQueue.pop();

		int r = here.row;
		int c = here.col;
		printf("(%d,%d)", r, c);
		if (map[r][c] == 'x') {
			printf("미로탐색 성공\n");
			return;
		}
		else {
			map[r][c] = '.';
			if (isValidloc(r - 1, c)) {
				locQueue.push(Location2D(r - 1, c));
			}
			if (isValidloc(r + 1, c)) {
				locQueue.push(Location2D(r + 1, c));

			}
			if (isValidloc(r, c - 1)) {
				locQueue.push(Location2D(r, c - 1));
			}
			if (isValidloc(r, c + 1)) {
				locQueue.push(Location2D(r, c + 1));
			}
		}
		printf("미로탐색 실패\n");
	}
}

큐미로에서 주의깊게 봐야 할 부분은

 

queue<Location2D> locQueue; // stack-> queue로 바뀜

Location2D here = locQueue.front(); // --> front()로 바뀜

locQueue.pop();

 

어떻게 해서든 길을 찾아가기는 하나 찾아가는 방식이 다릅니다! ( 깊이우선탐색과 너비우선탐색)

 

깊이우선탐색과 너비우선탐색의 차이점에 대해 설명해드릴게요

깊이우선탐색은 일단 최대한 갈 수 있는데 까지 가보고 막히면 다시 다른 길을 찾는 방식이구요

너비우선탐색은 탐색 순서에서 깊이보단 너비를 우선으로 취하는 방식입니다~

 

 

 

3. 덱을 이용한 미로탐색 

이번엔 덱을 이용해서 미로탐색 프로그램을 구현해내볼게요

덱은 스택과 큐의 성질을 둘다 가지고 있기 때문에 미로탐색을 하는 방식에도 깊이우선탐색과 너비우선탐색 총 2가지가 있습니다

 

 

 

 

 

일단 깊이우선탐색 방법부터 살펴볼게요

(1) 덱을 이용한 미로탐색 ( 깊이 우선탐색 )

덱을 이용한 미로탐색(깊이우선탐색)

#include "Location2D.h"
#include <deque> //STL deque
using namespace std;
const int MAZE_SIZE = 6;
char map[MAZE_SIZE][MAZE_SIZE] = {
		{'1','1','1','1','1','1'},
{'e','0','1','0','0','1'},
{'1','0','0','0','1','1'},
{'1','0','1','0','1','1'},
{'1','0','1','0','0','x'},
{'1','1','1','1','1','1'},
};
bool isValidloc(int r, int c) {
	if (r < 0 || c < 0 || r >= MAZE_SIZE || c >= MAZE_SIZE) {
		return false;
	}
	else {
		return map[r][c] == '0' || map[r][c] == 'x';
	}

}
void main() {
	deque<Location2D>locDeque; // deque
	Location2D entry(1, 0);
	locDeque.push_front(entry); 

	while(locDeque.empty() == false) {
		Location2D here = locDeque.front();
		locDeque.pop_front(); //덱 상단 객체를 삭제한다

		int r = here.row;
		int c = here.col;
		printf("(%d,%d)", r, c);
		if (map[r][c] == 'x') {
			printf("미로탐색 성공\n");
			return;
		}
		else {
			map[r][c] = '.';
			if (isValidloc(r - 1, c)) {
				locDeque.push_front(Location2D(r - 1, c));
			}
			if (isValidloc(r + 1, c)) {
				locDeque.push_front(Location2D(r + 1, c));

			}
			if (isValidloc(r, c - 1)) {
				locDeque.push_front(Location2D(r, c - 1));
			}
			if (isValidloc(r, c + 1)) {
				locDeque.push_front(Location2D(r, c + 1));
			}
		}
		printf("미로탐색 실패\n");
	}
}

 

 

(2) 덱을 이용한 미로탐색 프로그램(너비 우선 탐색)

#include "Location2D.h"
#include <deque>
using namespace std;
const int MAZE_SIZE = 6;
char map[MAZE_SIZE][MAZE_SIZE] = {
		{'1','1','1','1','1','1'},
{'e','0','1','0','0','1'},
{'1','0','0','0','1','1'},
{'1','0','1','0','1','1'},
{'1','0','1','0','0','x'},
{'1','1','1','1','1','1'},
};
bool isValidloc(int r, int c) {
	if (r < 0 || c < 0 || r >= MAZE_SIZE || c >= MAZE_SIZE) {
		return false;
	}
	else {
		return map[r][c] == '0' || map[r][c] == 'x';
	}

}
void main() {
	deque<Location2D>locDeque;
	Location2D entry(1, 0);
	locDeque.push_back(entry);

	while(locDeque.empty() == false) {
		Location2D here = locDeque.front();
		locDeque.pop_front();

		int r = here.row;
		int c = here.col;
		printf("(%d,%d)", r, c);
		if (map[r][c] == 'x') {
			printf("미로탐색 성공\n");
			return;
		}
		else {
			map[r][c] = '.';
			if (isValidloc(r - 1, c)) {
				locDeque.push_back(Location2D(r - 1, c));
			}
			if (isValidloc(r + 1, c)) {
				locDeque.push_back(Location2D(r + 1, c));

			}
			if (isValidloc(r, c - 1)) {
				locDeque.push_back(Location2D(r, c - 1));
			}
			if (isValidloc(r, c + 1)) {
				locDeque.push_back(Location2D(r, c + 1));
			}
		}
		printf("미로탐색 실패\n");
	}
}

 

지금까지 이니였습니다

출처 : c++로 쉽게 풀어쓴 자료구조