[BaekJoon] 2206 벽 부수고 이동하기 :: monton

문제

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

풀이

최단 거리를 구하는 것 이므로 bfs 사용

큐는 모두 3개가 필요한데 (x좌표, y좌표, 벽을 부순 횟수( 최대 1회 가능)) 이 세가지다

bfs를 이동하면서 상하좌우 방향으로 이동하는데 

상하좌우 뿐만아니라 다음 이동하는 원소가 1일 경우 벽을 부순 횟수를 1로 변경하여 계속해 나간다

중요한점은 visit[MAX][MAX][2]로 설정해야 한다.

visit에서 벽을 하나도 안부순 경우(0)와 벽을 이미 부수고 지나간 경우(1)를 체크해 준다

코드

#include <iostream>
#include <queue>
using namespace std;
 
int N, M,ans=1;
int arr[1001][1001];
int visit[1001][1001][2];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        //getchar();
        for (int j = 0; j < M; j++) {
            scanf("%1d",&arr[i][j]);
        }
    }
 
    queue<int> qx, qy, qn;
    qx.push(0), qy.push(0), qn.push(0);
    visit[0][0][0] = 1;
 
    while (!qx.empty()) {
        int qsize = qx.size();
        while (qsize--) {
            int x = qx.front();
            int y = qy.front();
            int n = qn.front();
            qx.pop(), qy.pop(), qn.pop();
 
            if (x == N - 1 && y == M - 1) {
                cout << ans;
                return 0;
            }
 
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                int nn = n;
 
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (visit[nx][ny][nn]) continue;
                if (nn&&arr[nx][ny]) continue;
 
                qx.push(nx), qy.push(ny);
 
                if (!nn&&arr[nx][ny]) qn.push(1), visit[nx][ny][1] = 1;
                else qn.push(nn), visit[nx][ny][nn] = 1;
            }
        }
        ans++;
    }
    cout << "-1";
}