벽 부수고 이동하기 3

백준 16933번: 벽 부수고 이동하기 3

아이디어

벽 부수고 이동하기 2 문제를 조금만 응용하면 풀 수 있다. 우선 벽에 가로막혔을 경우 낮이면 벽을 뚫고 지나가고, 밤이면 기다린다. 이 때 지금이 낮인지 밤인지, 그리고 몇 번 기다렸는지를 함께 기록해서 BFS한다. 마지막 답을 구할 때 기다린 횟수만큼 더해주면 정답이다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef struct _data {
    int y, x, cnt;
    bool day;
    int wait;
} Data;

int N, M, K, MIN = 987654321;
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};

bool wall[1000][1000];
int m[1000][1000][11];

void solve() {
    queue<Data> q;
    q.push({0, 0, 0, 1, 0});
    m[0][0][0] = 1;
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        bool day = q.front().day;
        int wait = q.front().wait;
        
        if (y == N-1 && x == M-1) {
            MIN = m[y][x][cnt] + wait;;
            break;
        }
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
            if (wall[ny][nx] && cnt < K && !m[ny][nx][cnt+1]) {
                if (day) {
                    m[ny][nx][cnt+1] = m[y][x][cnt] + 1;
                    q.push({ny, nx, cnt+1, !day, wait});                    
                }
                else {
                    q.push({y, x, cnt, !day, wait+1});
                }
            }
            else if (!wall[ny][nx] && !m[ny][nx][cnt]) {
                m[ny][nx][cnt] = m[y][x][cnt] + 1;
                q.push({ny, nx, cnt, !day, wait});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    char x;
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++){
            cin >> x;
            if (x == '1') wall[i][j] = true;
        }
    }
    solve();
    if (MIN == 987654321) cout << -1;
    else cout << MIN;
    return 0;
}

여담

C++에서 tuple 쓰기가 너무 불편하다. 그냥 구조체 만들어서 쓰는게 훨씬 나은듯? 물론 정렬할 일이 있으면 tuple을 사용하겠지만