[BOJ] 16933번 : 벽 부수고 이동하기 3 (C++)

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

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

 

벽 부수고 이동하기2 문제에서 낮,밤이라는 조건만 추가된 문제이다.

낮인지 밤인지를 저장해줄 변수만 하나 더 추가하면 되는 문제라 풀이를 해결해내는 것이 벽 부수고 이동하기2 문제를 푼 사람이라면 그리 어려울 것 같지 않다.

 

다만, 맨 처음에 예제가 이해가 가지 않았다.

0010이면 낮,밤,낮,밤 이 순서로 생각한다면 3번째 인덱스에 도착했을 때는 낮이니깐 바로 벽을 부술 수 있고, 그러면 최단거리가 5가 아니라 4가 아닌가? 라고 생각하였다.

그러나 벽인지 확인하고 벽을 부수려고 할 때는 전의 칸의 낮,밤을 체크해야 한다. 

즉, 인덱스로 표현해보자면 [0]->[1] 낮이면서 벽이 아니었기에 잘 이동하였고 밤이 된다.

[1]->[2]은 벽을 만난 상황인데 현재는 밤이라서 벽을 부술 수 없다. 

그래서 하루를 기다리게 되는 것이다. 

 

벽을 만난 경우와 벽을 만나지 않은 경우로 나눌 수 있고, 벽을 만나지 않은 경우는 그냥 지나가면 된다.

그러나 벽을 만난 경우는 우선, 벽을 깬 횟수가 k번보다 작은지 확인해야 한다.

k번보다 작아서 벽을 부술 수 있다면 낮인지 밤인지를 확인해야 한다.

낮이면 바로 깨면 되고, 밤이라면 하루 기다리면 된다.

dist배열을 업데이트해줄 때는 그 값이 초기화값인지를 확인해줘야 한다. 

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
#define X first
#define Y second

int n,m,k;
string area[1003];
int dist[3][12][1003][1003];
//{d,k,i,j} : (i,j)에 k번 벽을 부수고 도착했는데 d가 1이면 낮, d가 0이면 밤임
queue <tuple<int,int,int,int>> q;

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

int BFS(){
    while(!q.empty()){
        int curD, curK, curX, curY;
        tie(curD,curK,curX,curY) = q.front();
        q.pop();

        if(curX==n-1 && curY==m-1) return dist[curD][curK][curX][curY];

        for(int dir=0; dir<4; dir++){
            int nx = curX+dx[dir];
            int ny = curY+dy[dir];

            if(nx<0||nx>=n||ny<0||ny>=m) continue;

            //벽을 만난 경우
            if(area[nx][ny]=='1'){
                //이미 k번 깼으면 더이상 깰 수 없음 
                if(curK>=k) continue;

                //낮인 경우 
                if(curD){
                    if(dist[1-curD][curK+1][nx][ny]!=0) continue;
                    dist[1-curD][curK+1][nx][ny]=dist[curD][curK][curX][curY]+1;
                    q.push({1-curD,curK+1,nx,ny});
                }
                //밤이면 기다리면 됨
                else{
                    if(dist[1-curD][curK][curX][curY]!=0) continue;
                    dist[1-curD][curK][curX][curY]=dist[curD][curK][curX][curY]+1;
                    q.push({1-curD,curK,curX,curY});
                }
            }
            //벽이 아닌 경우 (그냥 가면 됨)
            else if(area[nx][ny]=='0'){
                if(dist[1-curD][curK][nx][ny]!=0) continue;
                dist[1-curD][curK][nx][ny]=dist[curD][curK][curX][curY]+1;
                q.push({1-curD,curK,nx,ny});
            }
        }
    }

    return -1;
}

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

    cin>>n>>m>>k;
    for(int i=0; i<n; i++) cin>>area[i];

    dist[1][0][0][0]=1;
    q.push({1,0,0,0});
    
    cout<<BFS();

    return 0;
}