[백준] 2206 벽 부수고 이동하기

백준2206

큐에 (x,y),벽을 부쉈는지 여부의 정보를 포함한다.
벽을 1번은 뚫을 수 있으므로,

1. 벽인 경우인데 벽을 뚫지 않고 지나온 경우 뚫고 진행하는 경로
2. 벽인 경우인데 벽을 뚫고온 경우는 더이상 진행할 수 없으므로 pop
3. 통로인 경우는 그냥 진행, 벽을 뚫은 정보도 그대로 유지
   의 경우로 나누어 구현하였다.

#include <iostream>
#include <queue>
#define MAX 1000
using namespace std;

int N, M;
int map[MAX][MAX];
int count;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int visit[MAX][MAX][2]; //x,y,벽을 부쉈는지 여부
//이미 방문한 정점이더라도 벽을 부수고 왔는지, 벽을 부수지 않고 왔는지에 따라 서로 다른 경로가 됨

int BFS() {
	queue<pair<pair<int, int>, int>> q;
	//<x,y,벽뚫기>
	q.push(make_pair(make_pair(0, 0), 0)); // 시작점
	visit[0][0][0] = 1;

	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int w = q.front().second;
		q.pop();

		if (x == N - 1 && y == M - 1) return visit[x][y][w];

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			//맵을 벗어나거나 방문했으면 넘어감
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (visit[nx][ny][w]) continue;

			if (map[nx][ny] == 0) { //길 인 경우
				visit[nx][ny][w] = visit[x][y][w] + 1;
				//w는 그대로 유지
				q.push(make_pair(make_pair(nx, ny), w));
			}
			if (map[nx][ny] == 1 && w == 0) {
				//벽 인 경우인데 벽을 뚫지 않고 온 경우, 뚫고 진행
				//벽인 경우이고 벽을 뚫고 온 경우는 더이상 진행할 수 없으므로 pop 한다.
				visit[nx][ny][1] = visit[x][y][w] + 1;
				q.push(make_pair(make_pair(nx, ny), 1));
			}
		}
	}
	return -1;
}
int main() {

	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &map[i][j]);
		}
	}

	cout << BFS() << '\n';
	return 0;
}