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

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

14442번: 벽 부수고 이동하기 2

벽부수고 이동하기 시리즈 다 풀고 백트래킹 해야겠다. "벽 부수고 이동하기 1" 문제를 처음 풀  당시의 코드가 완전 개판이어서, 2번을 풀 수 없었는데, 이번에 "벽 부수고 이동하기 1" 문제를 풀고 2번을 보니 코드를 잘 짜서 그런지 활용하여 풀 수 있을 것 같았다. 

---

접근 방법

 

이전 문제에서 벽을 1개만 부술 수 있었는데, K개만큼 부술수 있게 되었다. 이전 문제에서 벽을 부순 갯수를 기록했으므로, visited[2][1001][1001] 에서 visited[11][1001][1001]  으로 늘려주면 된다. 10개까지 부순 상태를 기록해야 하므로. 

 

그런데 시간초과가 났다. 

if(deq.second<K && arr[nr][nc]==1){ //부수자
      q.push(mp(mp(nr,nc),deq.second+1));
      visited[deq.second+1][nr][nc]=1;
}

위의 코드에서, 벽을 부수는 경우 이미 (부순횟수+1)번 부숴서 방문 한 경우 방문할 필요가 없다.

추가로 생각이 든게, 부순횟수보다 적게 부숴서 방문 한 경우 방문 하지 않아도 되는데, 이걸 가지치기에 사용하면 시간이 더 줄어들 것 같다.

if(deq.second<K && arr[nr][nc]==1 && visited[deq.second+1][nr][nc]==0){ //부수자
      q.push(mp(mp(nr,nc),deq.second+1));
      visited[deq.second+1][nr][nc]=1;
}

 

---

풀이

 

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,K;
int arr[1001][1001];
int visited[11][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));
  visited[0][0][0]=1;
  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<K && arr[nr][nc]==1 && visited[deq.second+1][nr][nc]==0){ //부수자
          q.push(mp(mp(nr,nc),deq.second+1));
          visited[deq.second+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(){
  scanf("%d %d %d",&N,&M,&K);
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      scanf("%1d",&arr[i][j]);
    }
  }
  printf("%d",bfs());
}