백준 14442번 : 벽 부수고 이동하기 2 - BFS C++

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

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

 

BFS를 수행할 때 벽을 몇개 부쉈는지 체크해주어야 합니다.

 

방문을 체크하는 배열에도 벽을 부순 갯수를 추가해서 

 

ch [x좌표][y좌표][벽을 부순 개수]

 

현재 좌표에서 몇개의 벽을 부쉈는지 저장해주어야합니다.

 

그리고 BFS를 수행하면 쉽게 구할 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int n, m, k;

bool arr[1003][1003];
bool ch[1003][1003][11];

struct Node {
    int x, y, z,d;
};

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

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

    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            arr[i][j] = s[j-1] - '0';
        }
    }

    queue<Node> Q;
    ch[1][1][0] = 1;
	Q.push({ 1,1,0 ,1 });

    bool flag = false;
    while (!Q.empty()) {
        int x = Q.front().x;
        int y = Q.front().y;
        int z = Q.front().z;
        int d = Q.front().d;
        Q.pop();

        if (x == n && y == m) {
            flag = true;
            cout << d << '\n';
            return 0;
        }

        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 (arr[nx][ny] == 1) {
                if (z < k && ch[nx][ny][z + 1] == 0) {
                    ch[nx][ny][z + 1] = 1;
                    Q.push({ nx,ny,z + 1,d+1 });
                }
            }
            else {
                if (ch[nx][ny][z] == 0) {
                    ch[nx][ny][z] = 1;
                    Q.push({ nx,ny,z,d + 1 });
                }
            }
        }
    }

    if (!flag) {
        cout << -1 << '\n';
    }
   
    return 0;
}

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