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

코로나 확진 후 집에서 공부가 되지 않는 스타일이라 주구장창 놀기만 한 것 같다.

슬슬 블로그 운영 다시 해야겠다.

 

간단한 BFS문제였지만 오타때문에 맞왜틀을 1시간동안 하고 있던 문제다.

3차원 배열을 활용해서 벽을 부쉈으면 [][][1]쪽으로 이동해서 그쪽에서 부터 BFS를 돌리면 된다.

코딩 스타일이 cur.first.first 이렇게 전부 다 쓰는 스타일이라 여기서 까딱 실수해버리면 항상 맞왜틀 하고 있는 것 같다...

#include <bits/stdc++.h>
#define endl '\n'
#define pii pair<int, int>
using namespace std;

int graph[1001][1001];
int visited[1001][1001][2];
int n, m;
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };

int bfs(int x, int y) {
	visited[x][y][0] = 1;
	queue<pair<pii, int>> q;
	q.push({ {x, y}, 0 });
	int distance = 1;
	bool finished = false;
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		if (cur.first.first == n && cur.first.second == m) {
			return visited[cur.first.first][cur.first.second][cur.second];
		}
		for (int i = 0; i < 4; i++) {
			int nx = cur.first.first + dx[i];
			int ny = cur.first.second + dy[i];

			if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
			if (visited[nx][ny][cur.second]) continue;

			if (graph[nx][ny] == 1 && cur.second == 0) {
				visited[nx][ny][1] = visited[cur.first.first][cur.first.second][cur.second] + 1;
				q.push({ {nx, ny}, cur.second + 1 });
			}
			if (graph[nx][ny] == 0) {
				visited[nx][ny][cur.second] = visited[cur.first.first][cur.first.second][cur.second] + 1;
				q.push({ {nx, ny}, cur.second });
			}
			
		}
		distance++;
	}


	return -1;
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		string s; cin >> s;
		for (int j = 0; j < m; j++) {
			graph[i][j + 1] = s[j] - '0';
		}
	}

	int ans = bfs(1, 1);
	cout << ans << endl;

	return 0;
}