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

#문제

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

#풀이

BFS를 사용하여 풀어보았습니다.

처음에는 K개의 벽을 선택하고 해당 벽을 지운 후에 BFS를 돌릴려는 생각을 했으나...

입력되는 맵의 크기가 1000 * 1000에다가 벽을 지울 수 있는 최대 개수가 10개...

굉장히 시간초과 날만합니다... 그런데도 무식하게 진행했다는...

결국 3차원 배열에 저장하는 식으로 방향을 바꾸게 되었습니다.

dist[r][c][cnt] -> r : 행 , c : 열 , cnt : 벽을 부순 개수 -> 위치(r,c)에서 cnt만큼 벽을 부셨을 때, 움직인 거리를 저장해주었습니다.

최대 1000 * 1000 * 10 배열을 채우게 되므로 시간 안에 풀 수 있게 됩니다.

#코드

#include <iostream>
#include <queue>
using namespace std;
 
struct Pos {
    //r : 행, c : 열, cnt : 부순 벽의 개수
    int r,c,cnt;
};
int N,M,K;
int map[1001][1001];
int dist[1001][1001][11];
 
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
 
int findLoad(){
    queue<Pos> q;
    q.push({1,1,0});
    dist[1][1][0] = 1;
    while(!q.empty()){
        int r = q.front().r;
        int c = q.front().c;
        int cnt = q.front().cnt;
        //현재 위치가 출구일때 거리 출력
        if(r == N && c == M){
            return dist[r][c][cnt];
        }
        q.pop();
        for(int i = 0; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            int nCnt = cnt + 1;
            //맵 밖으로 나갔을 경우
            if(nr < 1 || nr > N || nc < 1 || nc > M) continue;
            //이미 방문한 경우
            if(dist[nr][nc][cnt] != 0) continue;
            
            //다음 위치가 벽이 아닐때
            if(map[nr][nc] == 0){
                dist[nr][nc][cnt] = dist[r][c][cnt] + 1;
                q.push({nr,nc,cnt});
            }
            //다음 위치가 벽일 때
            if(map[nr][nc] == 1 && nCnt <= K){
                dist[nr][nc][nCnt] = dist[r][c][cnt] + 1;
                q.push({nr,nc,nCnt});
            }
        }
    }
    //탈출구를 찾을 수 없을때는 -1 출력
    return -1;
}
 
int main(){
    cin >> N >> M >> K;
    for(int i = 1; i <= N; i++){
        string getRow;
        cin >> getRow;
        for(int j = 0; j < M; j++){
            map[i][j+1] = getRow[j] - '0';
        }
    }
    cout << findLoad() << endl;
    return 0;
}