백준 BOJ 16933 C++ 벽 부수고 이동하기 3

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
int board[1002][1002];
bool visited[1002][1002][12];

int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, 1, -1};

queue<tuple<int, int, int, int>> q;  // i, j, 벽 부순 횟수, 홀수: 낮 짝수: 밤

void solve() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) {
        string str;
        cin >> str;
        for (int j = 0; j < m; ++j) {
            board[i][j] = str[j] - '0';
        }
    }
    visited[0][0][0] = true;
    q.push({0, 0, 0, 1});
    while (!q.empty()) {
        int i = get<0>(q.front());
        int j = get<1>(q.front());
        int broken = get<2>(q.front());  // 벽 부순 횟수
        int cnt = get<3>(q.front());  // 이동 카운트
        q.pop();
        if (i == n - 1 && j == m - 1) {  // 목표 지점에 도달한 경우 조기 종료
            cout << cnt << '\n';
            return;
        }
        for (int dir = 0; dir < 4; ++dir) {
            int ni = i + di[dir];
            int nj = j + dj[dir];
            if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
                if (board[ni][nj] == 0) {  // 다음 경로가 벽이 아닌 경우
                    if (!visited[ni][nj][broken]) {
                        visited[ni][nj][broken] = true;
                        q.push({ni, nj, broken, cnt + 1});
                    }
                } else {
                    if (broken < k) {  // 벽 부술 기회가 남아 있는 경우
                        if (cnt % 2 != 1) {  // 밤인 경우
                            q.push({i, j, broken, cnt + 1});  // 제자리 걸음
                        } else {  // 낮인 경우
                            if (!visited[ni][nj][broken + 1]) {  // 다른 탐색 경로에서 방문한 적이 없다면
                                visited[ni][nj][broken + 1] = true;
                                q.push({ni, nj, broken + 1, cnt + 1});  // 벽 부수고 이동
                            }
                        }
                    }
                }
            }
        }
    }
    cout << -1 << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}