이번 문제는 BFS 알고리즘을 활용하여 해결하는 문제였다.
DFS & BFS 알고리즘

• BFS함수 안에서 BFS에 이용할 큐를 생성한다. 이때 인자를 4개 두는데 순서대로 y,x,부순 블럭 수, 이동거리를 의미한다.
• 좌표의 이동은 dy, dx배열로 구현했다.
• 좌표가 나타내는 값이 1이고 부순 블럭 수가 0일때는 블럭을 부술 수 있기 때문에 블럭을 부수고 큐에 넣어준다.
• 방문 처리를 한다.

Code

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#define MAX 1001
using namespace std;

int n,m;
string line;
int graph[MAX][MAX];
bool visited[MAX][MAX][2];
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};

void Input(){
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>line;
        for(int j=0; j<m; j++){
            graph[i][j]=line[j]-'0';
        }
    }
}

int BFS(){
    queue<pair<pair<int, int>, pair<int, int>>> q;
    q.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
    visited[0][0][0]=true;
    while(!q.empty()){
        int y=q.front().first.first;
        int x=q.front().first.second;
        int block=q.front().second.first;
        int cnt=q.front().second.second;
        q.pop();
        if(y==n-1&&x==m-1)
            return cnt;
        for(int i=0; i<4; i++){
            int ny=dy[i]+y;
            int nx=dx[i]+x;
            if(ny>=0&&nx>=0&&ny<n&&nx<m){
                if(graph[ny][nx]==1&&block==0){
                    visited[ny][nx][block+1]=true;
                    q.push(make_pair(make_pair(ny,nx), make_pair(block+1, cnt+1)));
                }
                else if(graph[ny][nx]==0&&!visited[ny][nx][block]){
                    visited[ny][nx][block]=true;
                    q.push(make_pair(make_pair(ny, nx), make_pair(block, cnt+1)));
                }
            }
        }
    }
    return -1;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    cout<<BFS()<<endl;
    return 0;
}