https://www.acmicpc.net/problem/2206

✍️ 첫번째 접근

'만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개까지 부수고 이동하여도 된다.'를 어떻게 구현할 수 있을까 생각했는데 입력받은 NxM 맵에서 1이 있는 개수만큼 반복문으로 돌려서 한번씩 1이 있는 곳을 0으로 바꾸고 BFS를 돌리도록 하였다. 이렇게 구현하면서 시간 초과가 발생하지 않을까라고 생각하였는데 역시나 시간 초과가 발생하였다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
char board[1002][1002];
int dist[1002][1002];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<pair<int,int> > V;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> board[i][j];
            if(board[i][j] == '1')
                V.push_back(make_pair(i,j));
        }
    }
    int res = 10000;
    queue<pair<int,int> > Q;
    Q.push(make_pair(0,0));
    while(!Q.empty()) {
        pair<int,int> cur = Q.front();
        Q.pop();
        for(int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;
            if(board[nx][ny] == '1' || dist[nx][ny] > 0)
                continue;
            if(nx == n - 1 && ny == m -1) {
                res = dist[cur.X][cur.Y] + 2;
                cout << res;
                break;
            }
            Q.push(make_pair(nx,ny));
            dist[nx][ny] = dist[cur.X][cur.Y] + 1;
        }
    }

    for(int t = 0; t < V.size(); t++) {
        board[V[t].X][V[t].Y] = '0';
        for(int i = 0; i < n; i++)
            fill(dist[i],dist[i]+m,0);
        queue<pair<int,int> > Q2;
        Q2.push(make_pair(0,0));
        while(!Q2.empty()) {
            pair<int,int> cur = Q2.front();
            Q2.pop();
            for(int dir = 0; dir < 4; dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m)
                    continue;
                if(board[nx][ny] == '1' || dist[nx][ny] > 0)
                    continue;
                if(nx == n - 1 && ny == m -1) {
                    res = min(res,dist[cur.X][cur.Y] + 2);
                    break;
                }
                Q2.push(make_pair(nx,ny));
                dist[nx][ny] = dist[cur.X][cur.Y] + 1;
            }
        }        
        board[V[t].X][V[t].Y] = '1';
    }
    if(res == 10000)
        cout << -1;
    else
        cout << res;

    return 0;
}

✍️ 두번째 접근

첫번째 접근처럼 할 경우, 시간 초과가 발생하기 때문에 다른 접근 방식을 생각해야 한다.
3차원 배열로 선언해서 아직 벽을 안 부순 경우에 벽을 만났을 때 벽을 부술 수 있고 이 경우 3차원 배열 상에서 z축으로 이동한다. 여기서 z축은 벽을 부쉈는지 여부를 저장한다. 이미 벽을 부순 경우라면 더이상 벽을 부술 수는 없다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
char board[1002][1002];
int dist[1002][1002][2];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }
    
    queue<tuple<int,int,int> > Q;
    Q.push(make_tuple(0,0,0));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                dist[i][j][0] = dist[i][j][1] = -1;
    dist[0][0][0] = dist[0][0][1] = 1;
    while(!Q.empty()) {
        int x, y, broken;
        tie(x, y, broken) = Q.front();
        if(x == n-1 && y == m-1) {
            cout << dist[x][y][broken];
            return 0;
        }
        Q.pop();
        int next = dist[x][y][broken] + 1;
        for(int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;
            if(board[nx][ny] == '0' && dist[nx][ny][broken] == -1) {
                dist[nx][ny][broken] = next;
                Q.push(make_tuple(nx,ny,broken));
            }
            if(!broken && board[nx][ny] == '1' && dist[nx][ny][1] == -1) {
                dist[nx][ny][1] = next;
                Q.push(make_tuple(nx,ny,1));
            }
        }
    }
    cout << -1;

    return 0;
}