9. C++ 미로찾기(Queue, Maze)

Queue를 이용한 미로찾기 예제입니다.

 

1. "1"로만 이동 가능하고, 0은 이동 불가

 

1,1,0,0,0

0,1,1,1,1

0,0,1,1,1

0,0,0,0,1

 

2. 시작 (0,0)을 1로 할 때, (3,4)에서 탈출하면, 최단경로는 8.

 

3. 코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<vector<int>> ans;

void solution(vector<vector<int>> maze) {
	int dx[4] = {-1,1,0,0};
	int dy[4] = {0,0,-1,1};
	ans[0][0] = 1;
	queue<int> x;
	queue<int> y;

	x.push(0);
	y.push(0);

	int row, col;

	while (!x.empty()) {
		row = x.front();
		col = y.front();
		x.pop();
		y.pop();

		for (int i = 0; i < 4; i++) {
			int nx = row + dx[i];
			int ny = col + dy[i];
			
			if (nx < 0 || nx >= ans.size() || ny < 0 || ny >= ans[0].size())
			{
				continue;
			}
			if (maze[nx][ny] == 1) {
				x.push(nx);
				y.push(ny);
				maze[nx][ny] = 0;
			}
			else {
				continue;
			}
			ans[nx][ny] = ans[row][col] + 1;
			cout << ans[nx][ny] << endl;
		}



	}


}

int main() {
	vector<vector<int>> maze = { {1,1,0,0,0},{0,1,1,1,1},{0,0,1,1,1},{0,0,0,0,1} };
	vector<vector<int>> tmp(maze.size(), vector<int>(maze[0].size(), 0));
	ans = tmp;
	solution(maze);
	return 0;

}