평범한 BFS 문제와 비슷하지만 "부술 수 있는 벽"이라는 조건이 붙어 해결하지 못했다. 어느 순간에 벽을 부술지를 저장하는 새로운 배열을 만드는 것에 어려움을 느꼈고 결국 해답을 찾아보게 되었다.

오답

#include <iostream>
#include <deque>
#include <string>
#include <vector>

using namespace std;
int n, m;
int map[1010][1010];
int visited[1010][1010];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int result = 10000000;

void input()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> map[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            visited[i][j] = 0;
        }
    }
}

void solve() {
    deque<pair<int, int>> q;
    q.push_back(make_pair(0, 0));
    visited[0][0] = 1;
    int flag = 0;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        if (x == n && y == m) {
            if (visited[x][y] < result) {
                result = visited[x][y];
            }
        }
        q.pop_front();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 < nx <= n && 0 < ny <= m && map[nx][ny] == 1 && flag == 0 && visited[nx][ny] == 0) {
                flag = 1;
                visited[nx][ny] = visited[x][y] + 1;
                q.push_back(make_pair(nx, ny));
                flag = 0;
            }
            else if (0 < nx <= n && 0 < ny <= m && map[nx][ny] == 0 && visited[nx][ny] == 0) {
                visited[nx][ny] = visited[x][y] + 1;
                q.push_back(make_pair(nx, ny));
            }
        }
    }
    if (result == 10000000) {
        cout << "-1";
    }
    else {
        cout << result;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    input();
    solve();

}

정답 출처

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int maze[1000][1000][2];

int BFS(int N, int M)
{
    queue<pair<int, pair<int, int>>> q;
    q.push({ 0, { 0, 0 } });
    while (!q.empty())
    {
        int broken = q.front().first;
        int x = q.front().second.first;
        int y = q.front().second.second;
        q.pop();

        if (x == N - 1 && y == M - 1)
            return maze[N - 1][M - 1][broken] + 1;

        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 (maze[nx][ny][0] == 1)
            {
                if(!broken)
                {
                    maze[nx][ny][broken + 1] = maze[x][y][broken] + 1;
                    q.push({ 1, { nx, ny } });
                }
            }
            else if (maze[nx][ny][0] == 0) 
            {
                if (broken == 1 && maze[nx][ny][broken])
                    continue;
                maze[nx][ny][broken] = maze[x][y][broken] + 1;
                q.push({ broken, { nx, ny } });
            } 
        }
    }
    return -1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

	int N, M;
	cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            char tmp;
            cin >> tmp;
            maze[i][j][0] = tmp - '0';
        }
    }
    cout << BFS(N, M);
	return 0;
}