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

[적용한 알고리즘]

BFS

 

[아이디어]

낮과 밤을 토글을 이용해 하나의 정보로 또 넘겨주자.

 

[생각의 흐름 / 절차] 

뭔가 직관적으로 한거라 설명이 힘든데

사실 이동한 날의 수는 중요하지 않고, 거리만 중요하다.

낮이든 밤이든 비어있는 곳으로는 갈 수 있으니 어렵지 않다. 

 

문제는 낮에만 벽을 부술 수 있다는 것. 

현재 밤이면? -> 낮이 올 때까지 기다려야함. 

 

이걸 코드로 구현하는게 참 오래걸렸다. 

4차원 배열을 쓰는게 맞나싶긴하다. 

(어쨌든 맞았으니)

 

주석으로 보는게 나을 듯 하다.

 

[교훈]

열심히 살자

 

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
#include <tuple>
#define size 1001
using namespace std;

int n, m, k;
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, -1, 1};
int map[size][size];
int visited[size][size][11][2];
queue<tuple<int, int, int, int>> q;

bool inMap(int x, int y){
    if (1 <= x && x <= n && 1 <= y && y <= m) return true;
    return false;
}

int bfs(){
    //z = 0 이면 아직 벽을 한번도 안뚫은 상태
    //z = 1 이면 벽을 한 번 뚫은 상
    while (!q.empty()){
        int curx, cury, curz, move;
        tie(curx, cury, curz, move) = q.front();
        q.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inMap(nx, ny)){ // 다음에 방문할 곳이 map 안에 있다면
                //비어있는 곳으로 가는건 딱히 낮 밤에 구애 받지 않음.
                if (map[nx][ny] == 0 && visited[nx][ny][curz][(move + 1) % 2] == 0){
                    visited[nx][ny][curz][(move + 1) % 2] = visited[curx][cury][curz][move % 2] + 1;
                    q.push({nx, ny, curz, (move + 1) % 2});
                } // 다음 이동하는 곳에 벽이 없고, 아직 방문하지 않은 곳이라면

                // 벽을 부수고 싶은 경우
                if (move == 0){ // 현재 낮인 경우 -> 그냥 부숴버리면 됨
                    if (curz < k && map[nx][ny] == 1 && visited[nx][ny][curz + 1][(move + 1) % 2] == 0){
                        visited[nx][ny][curz + 1][(move + 1) % 2] = visited[curx][cury][curz][move % 2] + 1;
                        q.push({nx, ny, curz + 1, (move + 1) % 2});
                    }
                }
                else { // 현재 밤인 경우 -> 하루를 존버 타야함
                    // if 문에서 (move + 2) % 2 를 봐주는 이유는 (사실 move % 2 와 같지만 직관적으로 보이려고)
                    // 다음날 낮까지 존버를 탔을 때 그 다음날을 봐줘야하기 때문임.
                    if (curz < k && map[nx][ny] == 1 && visited[nx][ny][curz + 1][(move + 2) % 2] == 0){
                        visited[curx][cury][curz][(move + 1) % 2] = visited[curx][cury][curz][move % 2] + 1;
                        q.push({curx, cury, curz, (move + 1) % 2});
                    }
                }
            }
        }
    }

    int ans = 1000000000;
    bool flag = false;
    for (int i = 0; i <= k; i++){
        for (int j = 0; j < 2; j++){
            if (visited[n][m][i][j] > 0){
                flag = true;
                ans = min(ans, visited[n][m][i][j]);
            }
        }
    }
    if (flag) return ans;
    return -1;
}
int main(){
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            scanf("%1d", &map[i][j]);
        }
    }

    q.push({1, 1, 0, 0});
    visited[1][1][0][0] = 1;

    printf("%d\n", bfs());
    return 0;
}