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

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

16933번: 벽 부수고 이동하기 3

벽 부수고 이동하기 시리즈 3번째

---

접근 방법

 

벽 부수고 이동하기 2 문제와 비슷한데, 두 가지 조건이 추가되었다.

1. 밤과 낮이 번갈아가며 바뀌고, 낮에만 벽을 부술 수 있음.

2. 제자리에 머무를 수 있음

 

생각을 해보면, 최단 거리를 구하는 데 제자리에 머무르는 거는 도움이 되지 않는다. 그렇다면 언제 제자리에 머물러야하느냐? 바로 벽을 부숴야하는데 밤이라서 못 부수는 경우에만 머무르는 것이다. 

 

그래서 기존의 코드를 사용하고, 큐에 넣을 때 낮/밤 을 나타내는 변수를 하나 추가한다.

그리고 4방향을 조사하고, 제자리에 머무르는 코드를 추가한다. 이때, 제자리에 머무를 때 visited 배열을 어떻게 처리할지가 고민이 되었다. 그러나 제자리에 있어도 낮과 밤이 바뀌므로 1번 제자리에 있으면 이후에는 낮이 된 상태에서 큐에서 나온다. 그래서 낮에는 머무를수 없으므로 문제가 되지 않는다. 결론적으로 제자리에 머무름으로 인한 루프는 생기지 않고, 최대 한번만 자리에 머무르는 것이다. 

 

---

풀이

 

tag : bfs

#include<iostream> //16933
#include<queue>
#define piiii pair<pair<int,int>,pair<int,int>> //(r,c),(벽 부순 갯수, 낮밤01)
#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<piiii> q;
  int depth=1;
  q.push(mp(mp(0,0),mp(0,0)));
  visited[0][0][0]=1;
  while(!q.empty()){
    int qs=q.size();
    for(int i=0;i<qs;i++){
      piiii 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.first<K && arr[nr][nc]==1 && visited[deq.second.first+1][nr][nc]==0 && deq.second.second==0){ //부수자 낮에만
          q.push(mp(mp(nr,nc),mp(deq.second.first+1,1))); //밤 으로 추가
          visited[deq.second.first+1][nr][nc]=1;
        }
        if(arr[nr][nc]==0 && visited[deq.second.first][nr][nc]==0 ){ //갈수잇음
          int toggle= deq.second.second == 0 ? 1 : 0;
          q.push(mp(mp(nr,nc),mp(deq.second.first,toggle)));
          visited[deq.second.first][nr][nc]=1;
        }
      }
      if(deq.second.second==1){ //밤이면 머무르기, 낮에는 머무를 필요가없음
        int toggle= deq.second.second == 0 ? 1 : 0;
        q.push(mp(mp(deq.first.first,deq.first.second),mp(deq.second.first,toggle)));
      }
    }
    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());
}