[백준/BOJ] 2206 벽 부수고 이동하기 - 접근과 풀이 (c++)

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

2206번: 벽 부수고 이동하기

bfs를 처음 배울때 이 문제를 어렵게 풀었던 기억이 나서, 다시 풀어보았다. 

---

접근 방법

 

이 문제를 처음 풀때는, 모든 벽을 한번씩 만 부술 수 있으므로, 모든 벽을 한번씩 부숴보고 bfs를 돌렸었다. 결과는 당연히 TLE. 

최소의 값을 찾는 문제이므로, (0,0)에서 bfs를 돌린다. 그리고  탐색하면서 만나는 벽을 한번씩 부숴보는 것이다. 큐에 넣을 때 현재 위치와 벽을 부쉈는지 여부를 같이 저장한다. 핵심은, 벽을 부순 경우와 벽을 부수지 않은 경우의 visited 배열을 따로 사용해야한다.

---

풀이

tag : bfs

#include<iostream> //2206
#include<queue>
#define piii pair<pair<int,int>,int> //(r,c),벽부쉈는지 여부
#define mp make_pair
using namespace std;
int N,M;
int arr[1001][1001];
int visited[2][1001][1001]={0};
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int bfs(){
  queue<piii> q;
  int depth=1;
  q.push(mp(mp(0,0),0));
  while(!q.empty()){
    int qs=q.size();
    for(int i=0;i<qs;i++){
      piii deq=q.front();
      q.pop();
      if(deq.first.first==N-1 && deq.first.second==M-1)
        return depth;
      for(int j=0;j<4;j++){
        int nr=deq.first.first+dy[j];
        int nc=deq.first.second+dx[j];
        if(nr<0 || nc<0 || nr>=N || nc>=M)
          continue;
        if(deq.second==0 && arr[nr][nc]==1 && visited[0][nr][nc]==0){ //부수자
          q.push(mp(mp(nr,nc),1));
          visited[1][nr][nc]=1;
        }
        if(arr[nr][nc]==0 && visited[deq.second][nr][nc]==0){ //갈수잇음
          q.push(mp(mp(nr,nc),deq.second));
          visited[deq.second][nr][nc]=1;
        }
      }
    }
    depth++;
  }
  return -1;
}
int main(){
  cin>>N>>M;
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      scanf("%1d",&arr[i][j]);
    }
  }
  cout<<bfs();
}