백준 2206 벽 부수고 이동하기

백준 2206

벽을 안부시고 도달하는지, 부시고 도달하는지 전체적으로 체킹하기 위해서 방문 여부를 3차원 배열을 이용해서 만들어서 bfs를 돌린다.
이 때 2차원 배열만 이용해서 방문여부를 확인하면 벽을 부셨는지 여러개 부셔도 체크할 수 없다.

#include<bits/stdc++.h>
#define INF 987654321
using namespace std;
int n, m;
string arr[1001];
int vis[1001][1001][2];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) cin >> arr[i];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 2; k++) {
				vis[i][j][k] = -1;
			}
		}
	}

	queue<tuple<int, int, int>>q;

	q.push({ 0,0,0 });
	vis[0][0][0] = 1;

	while (!q.empty()) {
		int x, y, cnt;
		tie(x, y, cnt) = q.front();
		q.pop();

		if (x == n - 1 && y == m - 1) {
			cout << vis[x][y][cnt] << '\n';
			return 0;
		}
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

			if (vis[nx][ny][cnt]<0 && arr[nx][ny] == '0') {
				q.push({ nx,ny,cnt });
				vis[nx][ny][cnt] = vis[x][y][cnt]+1;
			}
			else if (arr[nx][ny] == '1' && cnt<1) {
				q.push({ nx,ny,cnt + 1 });
				vis[nx][ny][cnt+1] = vis[x][y][cnt] + 1;
			
			}
		}
	}
	cout << -1 << '\n';
}

처음에 방문여부를 2차원 배열로만 만들고, queue에서 tuple을 이용해서 좌표와 벽을 부셨는지 안부셨는지 체크해서 풀려고 했는데 틀렸다.
생각해보니 방문여부를 2차원 배열로만 설정하면 만약 하나의 길 밖에 없는데, 그 길을 가려면 무조건 거쳐야 하는 곳이 있다고 가정해보자
그럼 벽을 부셔서 방문했을 때 체크하면 돌아서 갔을 때 중복 체크 돼서 도착지까지 갈 수 있는 길이 있음에도 이미 무조건 가야하는 곳을 방문을 했다고 체크해서 그 곳을 지나서 가지 못해 길이 없다는 답을 도출할 수 있다.