[recursion 응용] 미로찾기

recursion을 응용하여 "미로찾기" class와 코드를 짜보자.

 

 

pathway를 통해 입구에서 출구로 가는 미로찾기

 

 

현재 위치에서 출구까지의 경로가 있기 위한 IDEA

1. 현재 위치가 출구여야 한다.  또는 

2. 이웃한 셀들 중 하나에서 현재위치를 지나지 않고 출구까지 간다.

 

 

---

1. Decision Problem 

답이 yes or no인 문제로 표현해보자.

bool findPath(x, y) {
	if (x, y) is the exit
		return true;
	else
		for each neighbouring cell(X, Y) of(x, y) do
			if (X, Y) is on the pathway
				if findPath(X, Y)
					return true;
		return false;
}

-> 이 코드는 X,Y에서 인접한 x,y로 다시 갈 수 있기 때문에, 무한루프에 빠질 가능성이 있다.

따라서 이미 방문한 위치를 구분하여 방문한 곳은 안 가도록 추가해야한다.

 

 

2. 이미 방문한 위치를 안가도록 설정하기

bool findPath(x, y) {
	if (x, y) is either on the wall or a visited cell
		return false;
	else if (x, y) is the exit
		return true;
	else {
		mark(x, y) as a visited cell;
		for each neighboring cell(X, Y) of(x, y) do
			if findPath(X, Y)
				return true;
		return false;
	}
}

->2번째 줄에 추가했다.

 

* 벽과 이미 간 셀이 아닌 경우에, exit를 찾을 때까지 인접한 (X,Y)로 가게 해 recursion을 돌리는 형태로 만들었다.

 

 

 

3. 미로 코드 완성하기

미로 코드의 IDEA

1) 지나갈 수 있는 길은 white와 1로,

지나갈 수 없는 길은 blue와 0으로,

이미 방문했는데 출구로 향하는 통로가 없는 길은 red와 2로,

방문했는데 어떤지 모르는 길은 green과 3으로 표시한다.

 

2) 또한 N*N미로 이므로 위치가 N이상이거나 0이하이면 범위를 벗어난 것으로 간주한다.

 

3) 인접한 셀들을 조사할 때 북-동-남-서 순으로 조사하는 것으로 한다.

 

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
class Maze {
private:
	int N = 8;
	int maze[8][8] = {
		{0,0,0,0,0,0,0,1},
		{0,1,1,0,1,1,0,1},
		{0,0,0,1,0,0,0,1},
		{0,1,0,0,1,1,0,0},
		{0,1,1,1,0,0,1,1},
		{0,1,0,0,0,1,0,1},
		{0,0,0,1,0,0,0,1},
		{0,1,1,1,0,1,0,0}
	};
	int PATHWAY_COLOUR = 0;//white
	int WALL_COLOUR = 1;//blue
	int BLOCKED_COLOUR = 2;//red
	int PATH_COLOUR = 3;//green

public:
	
	bool findMazePath(int x, int y) {
		int** maze;
		maze = new int* [N];
		for (int i = 0; i < N; i++)
			maze[i] = new int[N];

		if (x < 0 || y < 0 || x >= N || y >= N)
			return false;
		else if (maze[x][y] != PATHWAY_COLOUR)
			return false;
		else if (x == N - 1 && y == N - 1) {
			maze[x][y] = PATHWAY_COLOUR;
			return true;
		}
		else {
			maze[x][y] = PATHWAY_COLOUR;
			if (findMazePath(x - 1, y) || findMazePath(x, y + 1)
				|| findMazePath(x + 1, y) || findMazePath(x, y - 1)) {
				return true;
			}
			maze[x][y] = BLOCKED_COLOUR;//dead end
			return false;
		}
		for (int i = 0; i < N; i++)
			delete[] maze[i];
		delete[] maze;

	}
	void printMaze(void){
		for (int j = 0; j < N; j++) {
			for (int i = 0; i < N; i++) {
				cout << maze[j][i] << " ";
			}
			cout << endl;
		}
	}
};

int main(string args[]) {
	Maze m;
	m.printMaze();
	m.findMazePath(0, 0);
	m.printMaze();
}

-> 클래스로 구현하고 main함수에서 사용하는 과정에서 꼬인 코드.

일단 아이디어를 기록해놓기 위해 올려놓겠다.

코드가 완벽했더라면 이런식으로 이동했을 것이다.