2206번 벽 부수고 이동하기

문제를 풀기 전에, 시간복잡도를 계산하는 것은 중요하다. 그래야 단순히 브루트포스를 사용할 수 있는지, 추가로 고려해주어야 하는지를 판단할 수 있기 때문이다.
이 문제와 같은 경우에는, 벽이 최대 O(NM)일때, 하나씩 부수고 그때마다 탐색해야 한다고 치면 O((NM)^2)이다. 대충 1초에 1억을 돌 수 있다고 칠때, 1조가 계산되므로 절대 통과될 수 없다.
따라서 일일이 체크하는 방식으로는 풀 수 없다.

초기에 작성한 코드이다. 시간초과가 뜬다.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int map[1001][1001];
string arr[1001];
int ch[1001][1001];
int n, m;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int res = 2147000000, cnt=0;
struct Loc {
	int x, y;
	Loc(int a, int b) {
		x = a;
		y = b;
	}
};
int BFS(int x, int y) {
	queue<Loc> Q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ch[i][j] = 0;
		}
	}
	//ch[x][y] = -1;
	Q.push(Loc(x, y));
	//cout << x << y << " ";
	while (!Q.empty()) {
		Loc tmp = Q.front();
		Q.pop();
		//cout << tmp.x << " " << tmp.y << '\n';
		if (tmp.x == n && tmp.y == m) {
			return ch[tmp.x][tmp.y]+1;
		}
		for (int i = 0; i < 4; i++) {
			int xx = tmp.x + dx[i];
			int yy = tmp.y + dy[i];
			//cout << dx[i] << " " << dy[i] << "------" << '\n';
			//cout << xx << " " << yy << "  ";
			if (xx<1 || xx>n || yy<1 || yy>m) continue;
			if (map[xx][yy] == 1) continue;
			if (xx == 1 && yy == 1) continue;
			if (ch[xx][yy] == 0) {
				Q.push(Loc(xx, yy));
				ch[xx][yy] = ch[tmp.x][tmp.y]+1;
			}
		}
		//cout << '\n';
	}
	return 2147000000;
}
int main() {
	ios_base::sync_with_stdio(false);
	//freopen("in1.txt", "rt", stdin);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		for (int j = 1; j <= m; j++) {
			map[i][j] = arr[i][j-1] - '0';
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i][j] == 1) {
				//cout << i << " " << j << "  ";
				map[i][j] = 0;
				cnt = BFS(1, 1);
				if (res > cnt) res = cnt;
				map[i][j] = 1;
			}
		}
	}
	if (res != 2147000000) cout << res << '\n';
	else cout << "-1" << '\n';
	return 0;
}

ch배열에 방문했는지의 여부를 추가해준다. 이러면 벽을 부수고 갔는지 여부까지 알 수 있다.
내가 계속해서 생각해왔던 BFS에서 중요한 것이 입력받은 map을 다차원적으로 생각해야 할 수 있어야 한다는 것이었는데(ch배열) 정확히 지적한 문제인것 같다. 많은 도움이 되었다.

#include <iostream>
#include <stdio.h>
#include <queue>

using namespace std;
int map[1001][1001];
int ch[1001][1001][2];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
struct Loc {
	int x, y, key;
	Loc(int a, int b, int c) {
		x = a;
		y = b;
		key = c;
	}
};
int main() {
	int n, m;
	//freopen("in1.txt", "rt", stdin);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	queue<Loc> Q;
	Q.push(Loc(1, 1, 0));
	ch[1][1][0] = 1;
	while (!Q.empty()) {
		Loc tmp = Q.front();
		Q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = tmp.x + dx[i];
			int yy = tmp.y + dy[i];
			for(int i=0;i<4;i++) {
				int xx = tmp.x + dx[i];
				int yy = tmp.y + dy[i];
				if (xx > n || xx<1 || yy >m || yy < 1) continue;
				if (map[xx][yy] == 0 && ch[xx][yy][tmp.key] == 0) {
					ch[xx][yy][tmp.key] = ch[tmp.x][tmp.y][tmp.key] + 1;
					Q.push(Loc(xx, yy, tmp.key));
				}
				if (tmp.key==0&&map[xx][yy] == 1 && ch[xx][yy][tmp.key+1] == 0) {
					ch[xx][yy][tmp.key + 1] = ch[tmp.x][tmp.y][tmp.key] + 1;
					Q.push(Loc(xx, yy, tmp.key + 1));
				}
			}
		}
	}
	if (ch[n][m][0] != 0 && ch[n][m][1] != 0) cout << min(ch[n][m][0], ch[n][m][1]) << '\n';
	else if (ch[n][m][0] != 0) cout << ch[n][m][0] << '\n';
	else if (ch[n][m][1] != 0) cout << ch[n][m][1] << '\n';
	else cout << -1 << '\n';
	return 0;
}