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

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

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

 

벽 부수고 이동하기

 

문제와의 다른 점은 벽을 1번이 아니라 k번 부술 수 있다는 점이다. 

똑같이 거리를 저장할 3차원 배열 dist를 만들었다. 

dist[k][x][y] : 벽을 k번 부수며 (x,y)까지 오는데 최단 거리

벽을 만난 경우는 부술 수 있는 횟수인 k번보다 적다면 벽을 부수고 나아가면 된다. 

항상 dist배열을 업데이트할 때는 그 값이 초기화값이 맞는지를 확인해줄 필요가 있다.

 

추가로 이 문제는 예제입력이 한줄에 띄어쓰기없이 나온다.

그래서 C++로 푼다면 이 부분을 유의해서 입력을 받아야 한다. 

 

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

int n,m,k;
string area[1003];
int dist[12][1003][1003];
queue<pair<int,pair<int,int>>> q; //{k,i,j} : (i,j)까지 k번 벽을 부수고 이동한 최단 경로

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

int BFS(){
    while(!q.empty()){
        auto cur = q.front();
        q.pop();

        int curK = cur.X;
        int curX = cur.Y.X;
        int curY = cur.Y.Y;

        if(curX==n-1&&curY==m-1) return dist[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'){
                //부술 수 있는 횟수보다 적게 부셨으면 벽을 부수고 나아감 
                //그리고 방문한 적이 없어야함
                if(curK<k&&dist[curK+1][nx][ny]==0){
                    dist[curK+1][nx][ny]=dist[curK][curX][curY]+1;
                    q.push({curK+1,{nx,ny}});
                }
            }
            //벽이 아닌 경우
            else{
                if(dist[curK][nx][ny]==0){ //방문한 적이 없어야함
                    dist[curK][nx][ny]=dist[curK][curX][curY]+1;
                    q.push({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[0][0][0]=1;
    q.push({0,{0,0}});
    cout<<BFS();

    return 0;
}