백준 14442 벽 부수고 이동하기 2 - C++, BFS

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

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int n, m, k;
int goX[4] = { 0, 0, 1, -1 };
int goY[4] = { 1, -1, 0, 0 };
int map[1001][1001];
int cost[1001][1001][11];

int BFS(){
    queue<pair<pair<int, int>, int>> q;
    q.push(make_pair(make_pair(0, 0), 0));
    cost[0][0][0] = 1;

    while(!q.empty()){
        int curX = q.front().first.first;
        int curY = q.front().first.second;
        int breakCnt = q.front().second;
        q.pop();

        if(curX == m-1 && curY == n-1)
            return cost[curY][curX][breakCnt];
        
        for(int i = 0; i < 4; i++){
            int nextX = curX + goX[i];
            int nextY = curY + goY[i];
                
            if(nextX >= 0 && nextX <= m-1 && nextY >= 0 && nextY <= n-1){
                if(breakCnt < k && map[nextY][nextX] == 1 && cost[nextY][nextX][breakCnt+1] == 0){
                    cost[nextY][nextX][breakCnt + 1] = cost[curY][curX][breakCnt] + 1;
                    q.push(make_pair(make_pair(nextX, nextY), breakCnt + 1));
                }
                else if(map[nextY][nextX] == 0 && cost[nextY][nextX][breakCnt] == 0){
                    cost[nextY][nextX][breakCnt] = cost[curY][curX][breakCnt] + 1;
                    q.push(make_pair(make_pair(nextX, nextY), breakCnt));
                }
            }
        
        }
    }
    return -1;
}

int main(){
    scanf("%d %d %d", &n ,&m, &k);

    for(int i = 0; i < n; i++){
        string temp;
        cin >> temp;
        for(int j = 0; j < m; j++)
            map[i][j] = temp[j] - '0';
    }

    printf("%d\n", BFS());
}

---

 이전 문제에서 벽 부수는 횟수를 할당할 수 있게 된 문제입니다. 계속해서 시간초과가 떴는데

cost[nextY][nextX][breakCnt] == 0

이런 구문을 넣어 시간 이득을 취하면 됩니다. 배열의 값이 0이라는건 아직 방문하지 않은 지점이라는 뜻이며 BFS에서 이후 방문하는건 구조상 횟수가 많은 경우이니 무시할 수 있게 됩니다.