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

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

전에 업로드 했던 글

사실 이 문제는 처음에 해결하고 나서 조금 찜찜한 상태로 놔두었던 문제,

두고두고 언젠가는 정복하겠다는 생각을 가지고 있었다.

처음 풀 때보다 발전된 지금, 더 넓은 시야로 이 문제를 풀어보기로 했다.

문제 접근

1. BFS 특성

BFS의 특성 중 특정 지점에서 BFS로 어떤 한 지점을 방문한다고 할 때,

첫 방문이 항상 최단 거리이다.

(조금만 생각해보면 당연한 사실이나,

처음에는 이 특성을 별로 생각하지 않고 문제를 풀었다.)

2. 경우의 수

어떤 지점에 벽이 없을 때에는 벽을 부수고 온 경우와,

벽을 부수지 않고 방문하는 경우가 있다.

이를 기록하기 위해서는 두가지 경우를 모두 기록하는 배열이 필요하다

3. 벽의 부서짐 여부를 판단

벽이 부서진 경우와 벽이 부서지지 않았을 때를 구분하는 변수가 필요하다.

따라서 BFS를 수행할 때 변수 3개가 필요하게 된다.

1. x좌표
2. y좌표
3. 벽의 부서짐 유무

이들을 종합하여 코드를 작성하면 다음과 같다.

#include <bits/stdc++.h>
#define INF 1e8
using namespace std;

bool graph[1001][1001];
bool vis[1001][1001][2];
int d[1001][1001][2];
int n,m;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

//ans is min value of two elem d[n-1][m-1][0,1]

void init(){
    for(int i=0;i<n;i++) for(int j=0;j<m;j++){
        d[i][j][0]=INF;
        d[i][j][1]=INF;
    }
}

void bfs(){
    queue<pair<int, pair<int, int>>> q; //state position
    d[0][0][0]=1;
    vis[0][0][0]=true;
    q.push({0,{0,0}});
    while(!q.empty()){
        int x=q.front().second.first;
        int y=q.front().second.second;
        bool b=q.front().first;
        q.pop();
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(n-1<nx || nx<0 || m-1<ny || ny<0) continue;
            if(vis[nx][ny][b]) continue;
            if(!graph[nx][ny]){
                d[nx][ny][b]=d[x][y][b]+1;
                vis[nx][ny][b]=true;
                q.push({b,{nx,ny}});
            }
            else{
                if(b) continue;
                d[nx][ny][1]=d[x][y][0]+1;
                vis[nx][ny][0]=true;
                q.push({1,{nx,ny}});
            }
        }
    }
    if(!vis[n-1][m-1][0] && !vis[n-1][m-1][1]){cout << -1; return;}
    cout << min(d[n-1][m-1][0],d[n-1][m-1][1]);
}

int main(){
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%1d",&graph[i][j]);
    init();
    memset(vis,false,sizeof(vis));
    bfs();
    return 0;
}