백준 14442 벽 부수고 이동하기 2 (C++)

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

BFS 변형문제이다. 우선 K에 맞춰 방문한 곳을 저장하기 위해 3차원 배열 visit를 사용했다. 반복문을 돌면서 방문하지 않은 곳이면 true로 바꿔주고 벽인 경우는 k 값을 올려서 큐에 push 해주었다.
이렇게 풀고도 계속해서 시간 초과가 났었어서 굉장히 곤란했었다.... 이유는 visit 배열 크기를 [1001][1001][11]로 주어서 시간 초과가 났던 것이었다. 평소 배열 크기를 안전하게 1씩 늘려서 주던 버릇때문에 일어난 일인데 이 부분은 조심해야겠다.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int N, M, K;
int A[1000][1000];
bool visit[1000][1000][10];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

int findRes() {
    queue<pair<pair<int, int>, pair<int, int>>> q;  // y,x,m,k
    q.push({ {0,0},{1,0} });
    visit[0][0][0] = true;

    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int m = q.front().second.first;
        int k = q.front().second.second;

        q.pop();

        if (y == N - 1 && x == M - 1)
            return m;

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
            if (visit[ny][nx][k]) continue;

            if (k < K && A[ny][nx] == 1) {
                visit[ny][nx][k + 1] = true;
                q.push({ {ny,nx},{m + 1,k + 1} });
            }
            else if (A[ny][nx] == 0) {
                visit[ny][nx][k] = true;
                q.push({ { ny,nx }, { m + 1,k } });
            }
        }
    }

    return -1;
}

void solution() {
    cout << findRes();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M >> K;

    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < M; j++) {
            A[i][j] = s[j] - '0';
        }
    }

    solution();

    return 0;
}