boj 2206

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

요구사항 : arr[0][0]에서 arr[n-1][m-1]로 이동하는 최단거리를 구해라.

조건
1. 통과할수 있는 길은 '0' 통과 못하는 길은 '1'
2. '1'을 한번 '0'으로 바꿀 수 있다.

시도해본 방법
1. '1'의 벽을 모두 queue에 넣고 해당 큐가 빌때까지 '1'을 '0'으로 바꾸고 길찾기 해서 arr[n-1][m-1]값찾고
다시 '0'을 '1'로 변경하고 다음 queue에 들어있는 '1'을 0으로 변경 하는 식으로 '1'을 '0'으로 바꾸고 탐색이 되는지 모든 경우의 수 탐색 - 시간초과

2. 재귀를 이용한 DFS를 사용- 메모리 초과가 발생함

3. queue를 2개 사용하여 해당 처음 queue를 돌리면서 '1'을 만나면 해당 좌표에 값을 더하나 다른 queue에 해당좌표를 추가하고 continue로 다음 탐색을 이어갔다.
   이후 다른 queue를 탐색하면서 다음 좌표가 현재 좌표의 값 +1 보다 큰 경우에만 다시 현재queue에 추가해서 돌렸다. - 성공

코드

#include <bits/stdc++.h>
#define X first
#define Y second

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

using namespace std;
int n,m;

int main(){
   ios::sync_with_stdio(0);
   cin.tie(0);

   cin>>n>>m;

   string s[n];
   queue<pair<int,int>> one;
   for(int i=0;i<n; i++)cin>>s[i];
   int ans = INT_MAX;
   int arr[n][m];
   fill(arr[0],arr[n],-1);
   queue<pair<int,int>> Q;
   Q.push({0,0});
   arr[0][0] =1;
   while(!Q.empty()){
       pair<int,int> cur =Q.front();Q.pop();
       for(int i=0; i<4; i++){
           int x = cur.X+dx[i];
           int y = cur.Y+dy[i];
           if(x<0||x>=n||y<0||y>=m)continue;
           if(s[x][y]=='1' && arr[x][y]==-1){
               one.push({x,y});
               arr[x][y] = arr[cur.X][cur.Y]+1;
               continue;
           }
           if(arr[x][y]!=-1)continue;
           arr[x][y] = arr[cur.X][cur.Y]+1;
           Q.push({x,y});
       }
   }
   while(!one.empty()){
       pair<int,int> cur = one.front(); one.pop();
       for(int i=0; i<4; i++){
           int x = cur.X+dx[i];
           int y = cur.Y+dy[i];
           if(x<0||x>=n||y<0||y>=m)continue;
           if(s[x][y]=='1'|| (arr[x][y]!=-1&&arr[x][y]<=arr[cur.X][cur.Y]+1))continue;
           arr[x][y] = arr[cur.X][cur.Y]+1;
           one.push({x,y});
       }
   }
//   for(int i=0; i<n; i++){
//       for(int j=0; j<m; j++){
//           cout<<arr[i][j]<<" ";
//       }
//       cout<<"\n";
//   }
   if(arr[n-1][m-1]!=-1){
       ans = min(ans,arr[n-1][m-1]);
   }

    if(ans==INT_MAX)cout<<-1;
    else cout<<ans;

}

bfs어렵덩...