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

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

 (1,1)에서 (n,m)까지의 최소 경로를 구하는 문제다. 

조건: 길은 0, 벽은 1로 표현되어 있으며 벽은 최대 1회까지 부술 수 있다.

평범하게 BFS로 구현하되 벽을 부순적이 있는지 확인할 수 있어야한다.

 예전에 https://www.acmicpc.net/problem/31404에서 특정위치에 반복해서 들어가는 것 뿐만 아니라 들어오는 방향까지 고려해서 3차원 배열을 이용하여 문제를 해결했었다. 똑같은 문제라고 생각했고 visited배열을 visited[x][y][cnt]로 설정하여 cnt에 벽을 부쉈는지 확인하는 배열을 추가했다.

 

배열이 3차원이 된 것만 빼면 나머지는 well-known한 BFS탐색이다.

#include <stdio.h>
#include <queue>
#include <tuple>
using namespace std;

int n,m,x,y,cnt,nx,ny,ans;
int map[1001][1001];
int visited[1001][1001][2];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
bool flag = false;

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            scanf("%1d", &map[i][j]);
        }
    }
    queue<tuple<int,int,int>> q;
    q.push(make_tuple(1,1,0));
    while(!q.empty()){
        auto [x,y,cnt] = q.front();
        q.pop();
        if(x == n && y == m){
            ans = visited[x][y][cnt]+1;
            flag = true;
            break;
        }
        for(int i = 0; i < 4; i++){
            nx = x + dx[i];
            ny = y + dy[i];
            if(nx <= 0 || ny <= 0 || nx > n || ny > m) continue;
            if(visited[nx][ny][cnt]) continue;
            if(map[nx][ny] == 0){
                visited[nx][ny][cnt] = visited[x][y][cnt] + 1;
                q.push(make_tuple(nx,ny,cnt));
            }
            else{
                if(cnt == 1) continue;
                visited[nx][ny][cnt+1] = visited[x][y][cnt] + 1;
                q.push(make_tuple(nx,ny,cnt+1));
            }
        }
    }
    if(flag) printf("%d", ans);
    else printf("%d", -1);
}