[BOJ] 14442 벽 부수고 이동하기 2

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

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

처음에는 뚫고 지나온 벽의 개수를  bfs를 돌면서 저장했다가 개수가 K가 될 경우 벽을 만나면 지나치지 못하게 식을 세웠다. 이렇게 세우니 벽을 나중에 뚫는 경우가 더 최소인 경우가 존재하여 틀렸습니다가 떴다. 그래서 bfs를 돌 때, 방문을 했어도 이번에 방문하는 거리가 최소라면 push가 되게 했는데 이래도 오류가 났다... 솔직히 어떤 반례가 존재하는지 잘 모르겠다...

그래서 다른 분들의 코드를 참조하였는데 K가 10 밖에 되지 않으므로 벽 0~K개를 뚫었을 때 목적지로 향하는 최솟값을 일일이 저장한 뒤 그중 최솟값을 출력하는 식으로 구현했다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define MAX 100000001
using namespace std;
int bfs(int i,int j);
int N,M,K;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int map[1000][1000];
bool visit[1000][1000][10];
vector<int> ans;
void bfs(){
    queue<pair<pair<int,int>, pair<int,int> > > q;
    q.push(make_pair(make_pair(0,0),make_pair(0,1)));
    visit[0][0][0]=true;
    while(!q.empty()){
        int y=q.front().first.first,x=q.front().first.second,cnt=q.front().second.first,d=q.front().second.second;
        q.pop();
        if(y==N-1&&x==M-1){
            ans.push_back(d);
            continue;
        }
        for(int i=0;i<4;i++){
            int ny=y+dy[i],nx=x+dx[i];
            if(0<=ny&&ny<N&&0<=nx&&nx<M){
                if(map[ny][nx]==1){
                    if(cnt+1<=K&&!visit[ny][nx][cnt+1]){
                        visit[ny][nx][cnt+1]=true;
                        q.push(make_pair(make_pair(ny,nx),make_pair(cnt+1,d+1)));
                    }
                }else{
                    if(!visit[ny][nx][cnt]){
                        visit[ny][nx][cnt]=true;
                        q.push(make_pair(make_pair(ny,nx),make_pair(cnt,d+1)));
                    }
                }
            }
        }
    }
}


int main(){
    cin>>N>>M>>K;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            scanf("%1d",&map[i][j]);
        }
    }
    bfs();
    if(ans.size()==0) cout<<-1;
    else{
        int a=MAX;
        for(int i=0;i<ans.size();i++) a=min(a,ans[i]);
        cout<<a;
    }
    return 0;
}