백준 벽 부수고 이동하기

1. 부수고 가는 것, 부수지 않고 가는 것 큐의 구조체에서 확인하기. 특이점 : 현재 벽을 부순 개수를 기준으로 더 전진하는지, 아니면 스킵하는지  판단하도록 합니다. 그리고 bfs 문제에서 시간을 줄일 수 있는 방법은 dp 를 사용하던지, visit 를 고차원으로 사용하던지 입니다. 먼저 visit 를 손보고, 이것으로 안되면 dp를 사용하도록 하면 됩니다.  메모리 초과는 거의 나지 않기 때문에 걱정 노노 지금 10 * 1000 * 1000 을 해도 나지 않습니다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;
#define SIZE 6 // 1000
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int x, y, nx, ny;
int map[SIZE][SIZE];
int visit[11][SIZE][SIZE];
int result;
int N, M;
int dis;
string str;
struct point {
    int x, y, cnt, dis;
};
queue<point> que;
int cnt;
bool reach;
int k;
 
void problemIn() {
    cin >> N >> M >> k;
    for (int i = 0; i < N; i++) {
        cin >> str;
        for (int j = 0; j < M; j++) {
            map[i][j] = str[j] - '0';
        }
    }
}
 
void bfs() {
 
    while (!que.empty()) {
        reach = false;
        x = que.front().x;
        y = que.front().y;
        cnt = que.front().cnt; // 벽을 깬 횟수
        dis = que.front().dis;
        que.pop();
 
        if (x == N - 1 && y == M - 1) {
            reach = 1;
            result = dis;
            break;
        }
 
        for (int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if (nx >= N || ny >= M || nx < 0 || ny < 0) continue;
            if (visit[cnt][nx][ny]) continue; // 지나간적이 있으면 지나가기. 
            if (map[nx][ny] == 1) { // 옆이 1인데
                if (cnt >= k) continue; // 현재 깬적이 있으면 continue
                visit[cnt][nx][ny] = 1;
                que.push({ nx,ny, cnt + 1, dis + 1 });
            }
            else {
                visit[cnt][nx][ny] = 1; // 옆이 0 이면
                que.push({ nx,ny,cnt, dis+1 });
            }
        }
//    if (reach) return;
    }
}
 
 
 
void solve() {
    visit[0][0][0];
    que.push({ 0, 0, 0, 1});
    result = 1;
    bfs();
 
    if (reach) cout << dis<< endl;
    else cout << "-1" << endl;
}
 
 
int main() {
    problemIn();
    solve();
    return 0;
}