이번 문제는 BFS 알고리즘을 활용하여 해결하는 문제였다.
DFS & BFS 알고리즘
#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;
}