[BOJ/16933번벽부수고이동하기3] c++ /

문제

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

-벽 K개를 부술 수 있음 

-낮과 밤이 존재함

-낮에만 벽 부수고 이동가능

-이동하거나 제자리에 머무를 수 있음 ( 이동하지 않아도 하루가 지났다고 봄 )

-한가지 동작(이동, 제자리) 수행하면 낮밤이 바뀜

 

생각

벽부수고 이동하기 2에서 낮과 밤이라는 조건이 더 붙음

낮밤 변수 써서 풀면 되겠다 생각함

처음에 vis에 낮밤 차원을 하나 더 만들어서 풀었는데 뭔가 안됨

큐에서 팝 될 때 낮밤이 다 다를건데 그걸 고려하지 못함

해결법은 큐를 푸쉬할 때 낮밤 정보를 주는것 !!

 

문제풀이

1. 일단 bfs 문제랑 똑같음

2. 낮이라면, 

-1) 벽이 아님 & 방문표시 없음 : 방문표시 & 큐에 푸쉬 ( nx, ny, B, cnt+1, 밤 )

-2) 벽 & 방문표시 없음 & B < K ( 벽을 부술 수 있음 ) : 방문표시 & 큐에 푸쉬 ( nx, ny, B+1, cnt+1, 밤 )

3. 밤이라면, 

-1) 벽이 아님 & 방문표시 없음 : 방문표시 & 큐에 푸쉬 ( nx, ny, B, cnt+1, 낮 )

-2) 벽 & 방문표시 없음 & B < K ( 벽을 부술 수 있음 ) : 큐에 푸쉬 ( x, y, B, cnt+1, 낮 ) -> 이동하지 않고 제자리에 있음

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

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

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define X first
#define Y second
int board[1001][1001];
int vis[1001][1001][11];
int N, M, K;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int BFS() {
    queue<pair<tuple<int, int, int>, pair<int, int>>> Q; // 순서대로 x, y, B, cnt, m/n
    Q.push({{0, 0, 0}, {1, 0}});
    vis[0][0][0] = 1;

    while (!Q.empty()) {
        int x = get<0>(Q.front().X);
        int y = get<1>(Q.front().X);
        int B = get<2>(Q.front().X);
        int cnt = Q.front().Y.X;
        int day = 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 ( day == 0 ) { // 낮인 경우
                if ( board[nx][ny] == 0 && vis[nx][ny][B] == 0 ) { // 벽이 아닌 경우
                    vis[nx][ny][B] = 1;
                    Q.push({{nx, ny, B}, {cnt+1, 1}});
                }
                else if ( board[nx][ny] == 1 && B < K && vis[nx][ny][B+1] == 0 ) { // 벽인 경우
                    vis[nx][ny][B+1] = 1;
                    Q.push({{nx, ny, B+1}, {cnt+1, 1}});
                }
            }
            else { // 밤인 경우
                if ( board[nx][ny] == 0 && vis[nx][ny][B] == 0 ) { // 벽이 아닌 경우
                    vis[nx][ny][B] = 1;
                    Q.push({{nx, ny, B}, {cnt+1, 0}});
                }
                else if ( board[nx][ny] == 1 && B < K && vis[nx][ny][B+1] == 0 ) { // 벽인 경우
                    Q.push({{x, y, B}, {cnt+1, 0}});
                }
            }
        }
    }
    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();
}