[백준] 14442번 벽 부수고 이동하기 2

[적용한 알고리즘]

BFS

 

[아이디어]

벽 부수고 이동하기 1과 동일

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

내용

 

<코드>

#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];
queue<tuple<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;
        tie(curx, cury, curz) = 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] == 0){
                    visited[nx][ny][curz] = visited[curx][cury][curz] + 1;
                    q.push({nx, ny, curz});
                } // 다음 이동하는 곳에 벽이 없고, 아직 방문하지 않은 곳이라면

                if (curz < k && map[nx][ny] == 1 && visited[nx][ny][curz + 1] == 0){
                    visited[nx][ny][curz + 1] = visited[curx][cury][curz] + 1;
                    q.push({nx, ny, curz + 1});
                } // 현재 벽을 부수지 않은 상태고, 다음에 갈 곳이 벽이고, 아직 방문하지 않은 상태라면
            }
        }
    }

    int ans = 1000000000;
    bool flag = false;
    for (int i = 0; i <= k; i++){
        if (visited[n][m][i] > 0){
            flag = true;
            ans = min(ans, visited[n][m][i]);
        }
    }
    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});
    visited[1][1][0] = 1;

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