[백준] 2206번 벽 부수고 이동하기 (C++)

2206번: 벽 부수고 이동하기

삼차원 배열로 벽을 부수지 않은 경우, 벽을 부순 경우를 나누어 계산한다.

 

1. 벽을 부수지 않은 경우[0][x][y]

벽을 만났을 때 -> 벽을 한 번 부숴도 되므로 [1][x][y]에 값 넣음

벽을 만나지 않았을 때 -> [0][x][y]에 값 넣음

 

2. 벽을 부순 경우[1][x][y]

벽을 만났을 때 -> 두번 이상 부술 수 없으므로 값을 넣지 않음

벽을 만나지 않았을 때 -> [1][x][y]에 값 넣음

 

큐도 두 개로 나누어 검사해준다.

두 큐가 empty한 경우 [0][N][M]과 [1][N][M] 중 더 작은 값을 출력한다.

둘 다 값이 갱신되지 않았으면 -1을 출력한다.

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
int map[1001][1001], res[2][1001][1001] = { 0 }, dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
bool visited[2][1001][1001] = { false };
queue <pair<int, int>> q0, q1, temp0, temp1;
int success = -1, x, y;
void Bfs(int N, int M) {
	while (1) {
		while (!q0.empty()) {
			for (int i = 0; i < 4; i++) {
				x = q0.front().first + dx[i], y = q0.front().second + dy[i];
				if (x >= 1 && x <= N && y >= 1 && y <= M && map[x][y] == 0 && visited[0][x][y] == false) { //벽을 만나지 않았을 때
					res[0][x][y] = res[0][q0.front().first][q0.front().second] + 1;
					temp0.push(make_pair(x, y));
					visited[0][x][y] = true;
				}
				else if (x >= 1 && x <= N && y >= 1 && y <= M && map[x][y] == 1 && visited[0][x][y] == false) { //벽을 만났을 때
					res[1][x][y] = res[0][q0.front().first][q0.front().second] + 1;
					temp1.push(make_pair(x, y));
					visited[1][x][y] = true;
				}
			}
			q0.pop();
		}
		while (!temp0.empty()) {
			q0.push(make_pair(temp0.front().first, temp0.front().second));
			temp0.pop();
		}
		while (!temp1.empty()) {
			q1.push(make_pair(temp1.front().first, temp1.front().second));
			temp1.pop();
		}
		while (!q1.empty()) {
			for (int i = 0; i < 4; i++) {
				x = q1.front().first + dx[i], y = q1.front().second + dy[i];
				if (x >= 1 && x <= N && y >= 1 && y <= M && map[x][y] == 0 && visited[1][x][y] == false) { //벽을 만나지 않았을 때
					res[1][x][y] = res[1][q1.front().first][q1.front().second] + 1;
					temp1.push(make_pair(x, y));
					visited[1][x][y] = true;
				}
			}
			q1.pop();
		}
		while (!temp1.empty()) {
			q1.push(make_pair(temp1.front().first, temp1.front().second));
			temp1.pop();
		}
		if (q0.empty() && q1.empty()) {
			if (res[0][N][M] != 0 && res[1][N][M] != 0) success = min(res[0][N][M], res[1][N][M]);
			else if (res[0][N][M] != 0) success = res[0][N][M];
			else if (res[1][N][M] != 0) success = res[1][N][M];
			break;
		}
	}
}

int main() {
	int N, M;
	cin >> N >> M;
	string a;
	for (int i = 1; i <= N; i++) {
		cin >> a;
		for (int j = 1; j <= M; j++) map[i][j] = a[j - 1] - '0';
	}
	res[0][1][1] = 1;
	visited[0][1][1] = visited[1][1][1] = true;
	q0.push(make_pair(1, 1));
	Bfs(N, M);
	cout << success;
	return 0;
}