백준 g1 16933 벽 부수고 이동하기 3 c++

https://www.acmicpc.net/problem/16933

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

 

풀이

벽 부수고 이동하기 2(https://kyj0032.tistory.com/10)와 달라진 점은 낮과 밤이 생기고, 낮일 때만 벽을 부술 수 있다는 것이다.

 

if 다음 위치가 벽이 아닐 때

    평소처럼 bfs

else if 다음 위치가 벽일 때

    if 현재 시간이 낮이면 -> 벽 부수고 다음 위치로 이동

    else if 현재 시간이 밤이면 -> 현재 위치에서 낮까지 기다리기

/*boj g1 16933 벽 부수고 이동하기 3*/
#include <iostream>
#include <queue>
#include <tuple>
#define MAXN 1005
#define MAXK 12
#define MAXINT 999999999
using namespace std;

int N, M, K;
int vis[MAXN][MAXN][MAXK][2]; // x, y, k, night
int board[MAXN][MAXN];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void print() {
    cout << "\n==========day=========\n";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << vis[i][j][1][0] << " ";
        }
        cout << "\n";
    }

    cout << "\n=========night==========\n";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << vis[i][j][1][1] << " ";
        }
        cout << "\n";
    }
}

void input() {
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            char a;
            a = cin.get();
            while (a != '0' && a != '1')
                a = cin.get();

            board[i][j] = a - '0';
        }
    }
}

void bfs() {
    queue<tuple<int, int, int, int>> Q;

    Q.push(make_tuple(0, 0, 0, 1));
    vis[0][0][0][1] = 1;

    while (!Q.empty()) {
        auto [x, y, k, t] = Q.front();
        Q.pop();

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

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (board[nx][ny] == 0) { // 다음 이동할 위치가 벽이 아닐 때
                if (vis[nx][ny][k][nt] > 0) continue;

                vis[nx][ny][k][nt] = vis[x][y][k][t] + 1;
                Q.push({nx, ny, k, nt});
            } else if (board[nx][ny] == 1) { // 다음 이동할 위치가 벽일 때
                if (k + 1 > K) continue;
                if (vis[nx][ny][k + 1][0] > 0) continue; // 낮일 때 이미 있는 경우

                if (nt == 0) { // 다음 위치에 도착할 때가 낮이면
                    Q.push({nx, ny, k + 1, nt});
                    vis[nx][ny][k + 1][nt] = vis[x][y][k][t] + 1;
                } else { // 밤이면 현재 위치에서 한 번 기다리기
                    Q.push({x, y, k, nt});
                    vis[x][y][k][nt] = vis[x][y][k][t] + 1;
                }
            }
        }
        // print();
    }
}

void output() {
    int answer = 999999999;

    for (int k = 0; k < MAXK; k++) {
        for (int t = 0; t < 2; t++) {
            if (vis[N - 1][M - 1][k][t] != 0)
                answer = min(answer, vis[N - 1][M - 1][k][t]);
        }
    }

    if (answer == 999999999)
        answer = -1;

    cout << answer << "\n";
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    input();
    bfs();
    // print();
    output();
}

 

실수했던 것

1. 낮이 되면 동시에 부수고 이동하는 거 X, 낮일 때 앞 칸을 부술 수 있음 O

1 4 1
0010

answer : 5

이 예제를 봤을 때, 

0  0  1  0

낮밤 까지 왔을 때, 다음 날에 낮이 되면서 1인 벽을 부수고 갈 수 있을 거라 생각했지만 반대였다

낮일 때 앞에 있는 벽을 부술 수 있으므로, 첫번째 밤은 낮까지 기다려야 한다.

그래서 코드에서 맨 처음에 넣는 값을 0, 0, 0, 0 -> 0, 0, 0, 1(밤) 으로만 바꿔주었다.

 

2. 밤이고 앞 벽을 부술 때 처리

처음에는 밤이면 한 번 기다린 후에 부수고 이동하도록 하였다. 그러니 제출하자마자 틀렸다. 

} else { // 밤이면 한 번 기다린 후 부수고 이동
    Q.push({nx, ny, k + 1, 0});
    vis[nx][ny][k + 1][0] = vis[x][y][k][t] + 2;

 

이를 밑처럼 바꿔주었더니 통과되었다.

} else { // 밤이면 현재 위치에서 한 번 기다리기
    Q.push({x, y, k, nt});
    vis[x][y][k][nt] = vis[x][y][k][t] + 1;
}

 

한 번 기다릴 때 현재 위치를 +1 해주어야 하는지 아님 현재 위치는 놔두고 다음 위치에만 +2를 해줘야 하는지 고민을 했었다.

그러나 애초에 vis 배열을 잡을 때 낮밤 까지 모두 고려할 수 있도록 4차원 배열로 두었으므로 쓸모없는 고민이었다