[BOJ] 1261. 알고스팟

#include <iostream>
using namespace std;

int map[100][100];
int b_cnt[100][100];
int v[100][100];

int n,m;

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

void dfs(int x, int y, int _b_cnt){
    /*
     이미 x,y좌표에 기록된 최소의 Break Count보다
     현재 x,y좌표까지 오면서 Break Count가 더 많다면
     그 경우는 최적의 경우가 아니다.
     
     ex)
     b_cnt[1][1] = 0 인데
     돌고 돌아서 1,1을 왔는데 벽을 10개를 부수고 왔다.
     그렇다면 최적이 아니다.
     */
    if(b_cnt[x][y] <= _b_cnt)
        return;
    else
        b_cnt[x][y] = _b_cnt;
    
    
    if( x == n-1 && y == m-1 ){
        return ;
    }
    
    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(v[nx][ny]) continue;
        
        v[nx][ny] = 1;
        dfs(nx,ny, _b_cnt + (map[nx][ny] == 1 ? 1 : 0) );
        v[nx][ny] = 0;
    }
}

int main(){
    cin >> m >> n;
    for(int i=0; i<n; i++) for(int j=0; j<m; j++) b_cnt[i][j] = 2e9;
    for(int i=0; i<n; i++) for(int j=0; j<m; j++) scanf("%1d",&map[i][j]);
    
    v[0][0] = 1;
    dfs(0,0,0);
    
    cout << b_cnt[n-1][m-1] << endl;
    return 0;
}