[Backtracking] 미로 탈출

-Backtracking(백트래킹)

백트래킹은 brute force, DFS와 비슷하게 가능한 모든 방향을 탐색하는 알고리즘이다.
다만 DFS는 중간에 원하던 값이 아니더라도 무조건 트리의 리프노드까지 일단 갔다가 돌아오는 방식이고, 백트래킹은 내려가다가 중간에 원하던 값이 아닌 경우 바로 그전 단계로 되돌아오는 방식이다. (조금 더 효율적인 알고리즘)
관련 문제로는 미로찾기, N Queens, Subset Sum등이 있다.
 
 

-문제 설명

미로에서 탈출하는 경우의 수를 pathCnt로 계산해서 출력하는 문제이다. 0,0에서 시작해서 row-1,col-1로 도달하면 성공으로, 그때 pathCnt를 증가시킨다. 입력은 0과 1로 이루어진 행렬로 주어지며, '1'은 벽이고 '0'이 이동 가능한 통로이다.(int가 아니라 char로 들어옴) 동, 서, 남, 북 4가지 방향으로만 이동할 수 있으며 이미 방문한 칸은 다시 지나갈 수 없다.
 
 

-동작(c++)

• main
  • 미로 최대크기 알거나 동적으로 할 거면 배열로 -> 여기서는 사이즈 몰라도 괜찮은 벡터 사용 m(maze)
  • 방문한 칸은 지나갈 수 없다 하니 기록 저장 배열 필요 -> bool타입 visit 벡터 사용
  • 처음 시작 0, 0은 visit true로 표시하고 미로 탐색 시작 -> 재귀 필요하니 새 함수로 작성
• escapeMaze
  • 행(x) 열(y)마다 이동가능한 4방향 배열(moveX, moveY), 재귀적으로 증가시킬 pathCnt는 전역변수 선언(pathCnt는 escapeMaze 함수 안에서 지역변수로 선언해도 괜찮음 (이유는 밑에 설명))
  • 재귀함수이니 처음에 baseCase로 종료조건 반드시 선언 필수 -> end에 도달할 경우 카운터 증가시키고 return
  • 현재 위치는 방문 true상태로 만들기
  • 다음 위치로 이동할 칸 찾기 -> 동서남북 돌면서 벽이 아니고 방문한적 없으면 재귀 호출
    • 재귀호출로 계속 내려가다가 end 도달하면 baseCase if문에 걸려서 pathCnt증가시키고 return -> 그전 단계로 return 하면서 방문 표시 해제함(그 다음 경로 다시 찾아야 되니까)

<동작 예시>
0 0 0
0 1 0
0 0 0
====재귀 호출 과정====
(0, 0) : visit[0][0]: true  /  가능한 방향으로 동쪽 (0, 1) 재귀 호출
(0, 1) : visit[0][1]: true  /  가능한 방향으로 동쪽 (0, 2) 재귀 호출
(0, 2) : visit[0][2]: true  /  가능한 방향으로 남쪽 (1, 2) 재귀 호출
(1, 2) : visit[1][2]: true  /  가능한 방향으로 남쪽 (2, 2) 재귀 호출
(2, 2) : 도착, baseCase에 걸림, pathCnt++, return으로 이전 호출로 돌아감
====백트래킹 시작====
(1, 2) : visit[1][2]: false
(0, 2) : visit[0][2]: false
(0, 1) : visit[0][1]: false
(0, 0) : visit[0][0]: true  /  다시 여기서부터 가능한 방향(남쪽) 탐색 재귀 호출
...

 
 

-Code

#include <iostream>
#include <vector>
using namespace std;

int moveX[4] = { 0,1,0,-1 };
int moveY[4] = { 1,0,-1,0 };
int pathCnt = 0;

void escapeMaze(vector<vector<char>>& m, vector<vector<bool>>& visit, int x, int y, int row, int col) {
	if (x == row - 1 && y == col - 1) { //end
		pathCnt++;
		return;
	}
	visit[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int nextX = x + moveX[i];
		int nextY = y + moveY[i];

		if (nextX>=0 && nextY>=0 && nextX<row && nextY<col
			&& m[nextX][nextY]=='0' && !visit[nextX][nextY]) {
			escapeMaze(m, visit, nextX, nextY, row, col);
		}
	}
	visit[x][y] = false; //backtracking
}

int main()
{
	int row, col;
	cin >> row >> col;

	vector<vector<char>> m(row, vector<char>(col)); //maze
	vector<vector<bool>> visit(row, vector<bool>(col, false));

	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			cin >> m[i][j];
		}
	}

	visit[0][0] = true; //start

	escapeMaze(m, visit, 0, 0, row, col);
	cout << pathCnt;

	return 0;
}

 
 
 

---

-Code 2

pathCnt를 전역변수로 하지 않고 지역변수로 해도 가능

함수 자체를 int형으로 반환하도록 바꾼 다음, end일 때 1씩 return해서 재귀호출쪽에서 누적합하는 방식으로 구현하면 지역변수로 선언해도 가능하다. 
처음 코드를 보면 재귀 호출을 하면 그때마다 int pathCnt = 0; 라인을 만나서 그때마다 초기화 되니까 누적이 안되는 거 아닌가? 생각했지만... 과정을 생각해보면 새로 호출되는 함수들은 초기화돼도 상관이 없었다. 각 재귀 호출들은 독립적이고, 해당 함수가 끝날 때까지 pathCnt는 해당 호출에서만 유지되기 때문이다. 하위 호출로 이어지면서 그때마다 0으로 초기화 된 것들이 end를 만나면 1을 반환하면서 끝나고, 그럼 그 전 호출로 백트래킹 돼서 1을 가지고 있은 채로 for문을 돌다가 막혀서 끝나면 백트래킹 되면서 return으로 pathCnt를 반환할 것이다. 즉, 하위 호출에서 얻은 pathCnt들은 상위 호출로 올려 보내지는 형식이므로 그때그때마다 하위 호출에서 0으로 초기화 해도 문제가 없다는 뜻이다.
 

#include <iostream>
#include <vector>
using namespace std;

int moveX[4] = { 0,1,0,-1 };
int moveY[4] = { 1,0,-1,0 };

int escapeMaze(vector<vector<char>>& m, vector<vector<bool>>& visit, int x, int y, int row, int col) {
	if (x == row - 1 && y == col - 1) { //end
		return 1;
	}
	int pathCnt = 0;
	visit[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int nextX = x + moveX[i];
		int nextY = y + moveY[i];

		if (nextX>=0 && nextY>=0 && nextX<row && nextY<col
			&& m[nextX][nextY]=='0' && !visit[nextX][nextY]) {
			pathCnt += escapeMaze(m, visit, nextX, nextY, row, col);
		}
	}
	visit[x][y] = false; //backtracking
	return pathCnt;
}

int main()
{
	int row, col;
	cin >> row >> col;

	vector<vector<char>> m(row, vector<char>(col)); //maze
	vector<vector<bool>> visit(row, vector<bool>(col, false));

	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			cin >> m[i][j];
		}
	}

	visit[0][0] = true; //start

	cout<<escapeMaze(m, visit, 0, 0, row, col);

	return 0;
}

 

<동작 예시>
0 0
0 0
===재귀호출===
(0, 0) / pathCnt=0 
pathCnt += 다음 이동으로 (0, 1) 호출
pathCnt += 다음 이동으로 (1, 0) 호출

(0, 1) / pathCnt=0
pathCnt += 다음 이동으로 (1, 1) 호출 -> 도착, return 1;

(1, 0) / pathCnt=0
pathCnt += 다음 이동으로 (1, 1) 호출 -> 도착, return 1;

===백트래킹===
(0, 0)으로 돌아오면 
pathCnt = 1(0,1에서 반환된 값) + 1(1,0에서 반환된 값)
=> 최종적으로 return 2가 됨

 

사실 헷갈리니까 그냥 전역변수로 쓰는게 더 좋아보이기는 하다... 그래도 이 방법도 왜 되는지는 이해하고 싶어서 찾아봄