Baekjoon 14442번 벽 부수고 이동하기 2

문제

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

걸린 시간

00 : 34 : 39

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, m, k;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
vector<vector<int>> maze;
vector<vector<vector<int>>> visited;

struct node{
    int y, x, broke;
    node(int y, int x, int broke){
        this->y = y;
        this->x = x;
        this->broke = broke;
    }
};

int bfs(){
    visited.resize(n, vector<vector<int>>(m, vector<int>(k+1, 0)));
    queue<node> q;
    q.push(node(0, 0, 0));
    visited[0][0][0] = 1;
    int depth = 0;
    while(!q.empty()){
        depth++;
        int size = q.size();
        for(int i = 0; i < size; i++){
            int y = q.front().y;
            int x = q.front().x;
            int broke = q.front().broke;
            q.pop();
            if(y == n-1 && x == m-1) return depth;
            for(int j = 0; j < 4; j++){
                int ny = y+dy[j];
                int nx = x+dx[j];
                if(0 <= ny && ny < n && 0 <= nx && nx < m){
                    if(maze[ny][nx] == 1){
                        if(broke >= k) continue;
                        if(visited[ny][nx][broke+1]) continue;
                        visited[ny][nx][broke+1] = 1;
                        q.push(node(ny, nx, broke+1));
                    }
                    else{
                        if(visited[ny][nx][broke]) continue;
                        visited[ny][nx][broke] = 1;
                        q.push(node(ny, nx, broke));
                    }
                }
            }
        }
    }
    return -1;
}

int main(){
    cin >> n >> m >> k;
    maze.resize(n, vector<int>(m));
    for(int y = 0; y < n; y++)
        for(int x = 0; x < m; x++)
            scanf("%1d", &maze[y][x]);
    printf("%d\n", bfs());
    return 0;
}

벽 부수고 이동하기 문제에서 벽을 부술 수 있는 개수 k 가 추가되었다. 방문 배열의 3차원 축을 k+1 (부순 벽의 개수 + 부수지 않았을 때) 로 하여 bfs 를 진행하면 된다.