[BOJ / C++] #2206 벽 부수고 이동하기

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

문제풀이

1차 시도

입력을 받을 때 모든 벽들을 vector<pair<int,int>> walls 에 넣어놓고,
기존 map을 복사해놓고 좌표를 하나씩 꺼내어 0으로 만들어 벽을 부수고, BFS를 돌려 최단 경로를 구했다.
하지만. . 시간 초과 🥲
생각해보니 벽을 아무곳에나 뚫어놓고 전부 구해보면 된다고 생각했는데 시작점에서 인접방향으로 퍼지는 BFS 특성상,, 막혔을 때 뚫고 가지 않으면 어차피 그 뒤에 나오는 걸 뚫어도 의미 없다. .
한 번 뚫어놓고 또 나오는 벽은 어차피 못 가는 길인 것임.
따라서 벽이 나오면 바로 뚫어야 되는데 한 번밖에 뚫지 못하니깐 큐에 넣을 변수로는 현재 좌표와, 뚫었는지의 여부가 필요하다.
최단경로를 기록해놓을 visited 배열에도 마찬가지이다.

맨 처음 도착지점에 도달했을 때의 최단경로를 출력해주면 되는 것이다.

2차 시도

구글선생을 통해 새로운 방법으로 시도했다.

• 최단거리를 저장할 visited배열을 3차원으로 선언하여 행 좌표, 열 좌표, 벽을 부셨는지 여부 를 저장한다.

• 큐에 넣을 구조체도 (행 좌표, 열 좌표, 벽을 부셨는지 여부) 를 가진다. 현재 즉 현재 상태를 나타내게 된다.

• 처음에 (1,1)에서 벽을 부수지 않고 시작하기 때문에 큐에 Loc(1,1,false)를 push하고
  시작점도 거리에 포함하기 때문에 visited[1][1][false]=1이 된다.

• 이후 while(!q.empty())문을 도는데, 큐에서 꺼낸 구조체의 좌표가 (N,M)이 될 때 종료한다.

• 현재 좌표에서 인접방향 4방향을 돌면서

  1. 벽이고, 현재 아직 벽을 안부셨다면
     인접한 벽은 부셔주고 (visited[nr][nc][true]), visited배열 안에 들어가는 값은 현재 visited값+1이다.
     부순 후 큐에 넣어준다.

  2. 벽이 아니고 방문한 적 없다면
     isCrushed상태는 그대로 유지하면 된다.
     visited[nr][nc][isCrushed]=visited[r][c][isCrushed]+1;

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define MAX 1000+1

int N,M;
char map[MAX][MAX];
int visited[MAX][MAX][2]; // 3차원은 벽을 뚫었는지 여부!
int dr[4]={-1,0,1,0};
int dc[4]={0,1,0,-1};

struct Loc{
   int r,c;
   bool isCrushed;

   Loc(int rr,int cc, bool iisCrushed){
       r=rr;
       c=cc;
       isCrushed=iisCrushed;
   }
};

int bfs(){
   queue<Loc> q;
   q.push(Loc(1,1,false)); //(1,1)에서 시작, 아직 벽 안뚫음
   visited[1][1][false]=1;

   while(!q.empty()){
       int r=q.front().r;
       int c=q.front().c;
       bool isCrushed=q.front().isCrushed;
       q.pop();

       //도착
       if(r==N&&c==M){
           return visited[r][c][isCrushed];
       }

       for(int d=0;d<4;d++){
           int nr=r+dr[d];
           int nc=c+dc[d];
           if(nr<1||nr>N||nc<1||nc>M) continue;
           if(visited[nr][nc][isCrushed]) continue; //방문한 적 있다면


           //1.벽 이고, 아직 뚫은 적이 없다
           if(map[nr][nc]=='1'&&!isCrushed){
               visited[nr][nc][true]=visited[r][c][isCrushed]+1; //뚫고, 거리 더해주기
               q.push(Loc(nr,nc,true));
           }

           //2. 벽이 없다.
           else if(map[nr][nc]=='0'&&!visited[nr][nc][isCrushed]){
               visited[nr][nc][isCrushed]=visited[r][c][isCrushed]+1;
               q.push(Loc(nr,nc,isCrushed));
           }

       }
   }

   return -1;
}

int main(){
   cin>>N>>M;
   for(int i=1;i<=N;i++){
       for(int j=1;j<=M;j++){
           char val; cin>>val;
           map[i][j]=val;
       }
   }

   cout<<bfs()<<"\n";
   return 0;
}