BOJ 14442 벽 부수고 이동하기 2

www.acmicpc.net/problem/14442

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

 

기존 벽 부수고 이동하기 문제에선 오직 한 번만 벽을 부술 수 있었지만

2번 문제에선 총 10번까지 벽을 부술 수 있다.

따라서 기존 vis[MAX][MAX][2] 였던 배열을 vis[MAX][MAX][11]로 바꿔서 BFS 할 때 조금만 수정해주면 된다.

 

 

#include <iostream>
#include <string>
#include <queue>
using namespace std;
 
int n, m, k;
int vis[1001][1001][11];
string a[1001];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<pair<int, int>, int>> q;
 
int bfs() {
    vis[0][0][0] = 1;
    q.push({ {0,0},0 });
 
    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int block = q.front().second;
        q.pop();
        if (x == n - 1 && y == m - 1) return vis[x][y][block];
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (a[nx][ny] == '0') { //벽이 아니라면 block을 증가시킬 필요 없음
                if (!vis[nx][ny][block]) { //방문하지 않았다면
                    vis[nx][ny][block] = vis[x][y][block] + 1;
                    q.push({ {nx,ny},block });
                }
            }
            else { //벽이라면 부술 수 있음
                if (block < k && !vis[nx][ny][block + 1]) { //벽을 부술 수 있고 부술 곳을 방문하지 않았다면
                    vis[nx][ny][block + 1] = vis[x][y][block] + 1;
                    q.push({ {nx,ny},block + 1 });
                }
            }
        }
    }
    return -1;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) cin >> a[i];
 
    cout << bfs() << endl;
 
    return 0;
}