백준 2206 벽 부수고 이동하기 (C++)

2206번: 벽 부수고 이동하기

지난 번에 풀었던 벽 부수고 이동하기 2보다 쉬운 버전의 문제이다. 이전 문제와 굉장히 유사하게 풀었다. visit배열을 벽을 부순 유무를 추구한 3차원 배열로 구성하여 BFS를 돌면서 벽을 부수고 이동했는지 확인을 해주었다. 벽을 만나면 벽을 부수고 k=1인 상태로 바꾸어 다음에 벽을 만나면 지나가지 못하게 해주면서 길이를 구했다. 이번 문제는 어렵지 않게 풀 수 있었다.

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int N, M;
int A[1000][1000];
bool visit[1000][1000][2];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

int bfs() {
    queue<pair<pair<int, int>, pair<int, int>>> q;

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

    while(!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int m = q.front().second.first;
        int k = q.front().second.second;

        q.pop();

        if (y == N - 1 && x == M - 1) {
            return m;
        }

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
            if (visit[ny][nx][k]) continue;

            if (k == 0 && A[ny][nx] == 1) {
                visit[ny][nx][k + 1] = true;
                q.push({ {ny,nx},{m + 1,k + 1} });
            }
            else if(A[ny][nx]==0) {
                visit[ny][nx][k] = true;
                q.push({ {ny,nx},{m + 1,k} });
            }
        }
    }

    return -1;
}

void solution() {
    cout << bfs();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;

        for (int j = 0; j < M; j++) {
            A[i][j] = s[j] - '0';
        }
    }

    solution();

    return 0;
}