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;
}