[BOJ/14442번벽부수고이동하기2] c++ / BFS

문제

(1, 1)칸에서 (N, M)칸까지 가는 최단 경로를 구하는 문제

-벽 K개를 부술 수 있음 

 

생각

벽부수고 이동하기1 문제에 벽 개수만 늘리면 됨

 

문제풀이

1. 일단 bfs 문제랑 똑같음

2. 만약 해당 칸이 벽이라면,

-1) 벽을 부순 적이 있는지 확인

-2) 없을 경우, 큐에 push 해줌 ( vis[][][1] / 0은 벽을 부수지 않았을 때, 1은 벽을 부수었을 때의 방문칸을 나타냄 / B+1 해줌 )

3.만약 해당 칸이 벽이 아니라면

-1) 해당칸의 방문칸의 방문여부를 확인

-2) 방문하지 않았다면, 큐에 push 해줌 ( 2번 과정을 걸쳤다면 vis[][][1], 그렇지 않다면 vis[][][0] 임 / 그래서 그냥 B로 넘겨줌 )

4.반복문 돌다가 (N-1, M-1)칸까지 오면 cnt 출력하고 종료

5.반복문에서 벗어난다면 -1 출력

 

-시간초과 났는데, 2번 과정에서 방문했는지 조건 추가하면 시간초과 문제 해결됨

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define X first
#define Y second
int board[1001][1001];
int vis[1001][1001][10];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int N, M, K;
int BFS() {
    queue<pair<pair<int, int>, pair<int, int>>> Q;
    vis[0][0][0] = 1;
    Q.push({{0, 0}, {0, 1}});

    while (!Q.empty()) {
        int x = Q.front().X.X;
        int y = Q.front().X.Y;
        int B = Q.front().Y.X;
        int cnt = Q.front().Y.Y;
        Q.pop();
       
        if ( x == N-1 && y == M-1 )
            return cnt;

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

            if ( nx < 0 || nx >= N || ny < 0 || ny >= M ) continue;

            if ( board[nx][ny] == 1 && B < K ) { // 벽이 있고, 벽 부수기가 가능하다면
                if ( vis[nx][ny][B+1] ) continue;
                Q.push({{nx, ny}, {B+1, cnt+1}});
                vis[nx][ny][B+1] = 1;
            }
            else if ( board[nx][ny] == 0 && vis[nx][ny][B] == 0 ) { // 벽이 없고, 방문 표시가 없다면
                Q.push({{nx, ny}, {B, cnt+1}});
                vis[nx][ny][B] = 1;
            }
        }
    }

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

    cin >> N >> M >> K;
    for ( int i = 0; i < N; i++ ){
        string str;
        cin >> str;
        for ( int j = 0; j < M; j++ ) {
            int tmp = str[j]-'0';
            board[i][j] = tmp;
        }
    }
    cout << BFS();  
}