[BOJ] 2206. 벽 부수고 이동하기

#include <iostream>
#include <queue>
using namespace std;

int map[1000][1000];
int v[1000][1000][2];

int n,m;

int dx[] = {1,0,0,-1};
int dy[] = {0,1,-1,0};

struct Node{
    int x;
    int y;
    int time;
    int break_used; // Break했다면 True
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int ans = 2e9;
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        for(int j=0; j<m; j++){
            map[i][j] = s[j] - '0';
        }
    }
    
    Node node{0,0,1,0};
    queue<Node> q;
    q.push(node);
    v[0][0][0] = 1; // 0,0위치 Break하지 않은 상태로 방문했다.
    
    while (! q.empty()) {
        Node top = q.front();
        q.pop();
        int x = top.x;
        int y = top.y;
        int time = top.time;
        int break_used = top.break_used;
        
        if( x == n-1 && y == m-1 ){
            ans = time;
            break;
        }
    
        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;
            
            // 벽이 있고 Break 가능 상태
            if(map[nx][ny] == 1){
                if(break_used == 1) continue;
                if(! v[nx][ny][1]  ){
                    q.push(Node{nx,ny,time+1,1});
                    v[nx][ny][1] = 1;
                }
            } // end of if
            else{
                if(!v[nx][ny][break_used]){
                    q.push(Node{nx,ny,time+1, break_used});
                    v[nx][ny][break_used] = 1;
                }
            }
        }
    }
    
    if(ans == 2e9)
        ans = -1;
    cout << ans << endl;
    return 0;
}

 if( x == n-1 && y == m-1 ){
            ans = time;
            break;
        }