[Algorithm] 백준 2206번 : 벽 부수고 이동하기

 

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

2206번: 벽 부수고 이동하기

 

 

이 문제에서 어려웠던 부분은, 벽을 부수거나 안부술 수 있고, 그 기회는 오직 1번이라는 것!

 

dfs는 재귀로 경우 나눠서 풀면되는데

 

bfs에서 경우를 나누는 법이 도저히 생각이 안났다.

 

그러다가 힌트를 봄.

 

check(방문을 체크하는 배열)의 차원을 늘려서 

 

마지막 차원을 부쉈는지 여부를 넣어주면(0: 안부숨, 1: 부숨)

 

2가지의 방문 경우의 수가 생기고

 

벽을 마주칠 때 아직 부순 경험이 없다면

 

부수고 check의 마지막 차원이 1인 곳에 방문 표시를 해주고, 큐에 넣어주면 된다.

 

 

** 주의할 것 -> bfs 풀때 뭔가에 도달했을때 return하는거면 pop할때 조건확인하고 리턴하는걸로 하자 (이것때문에 몇시간을 날림)

 

 

 

 

Code

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

struct pos
{
    int x, y, dist, destroy;
};

int main() {
    int n, m;
    queue<pos> q;
    int check[1000][1000][2] = {0, }, v[1000][1000] = {0, };
    int mv[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    cin >> n >> m;

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

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

    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int dist = q.front().dist;
        int destroy = q.front().destroy;

        q.pop();

        // 도착했으면 리턴
        if(x == n-1 && y == m-1) {
            cout << dist;
            return 0;
        }
        
        for(int i=0; i<4; i++) {
            int nx = x + mv[i][0];
            int ny = y + mv[i][1];
            int ndist = dist + 1;
            
            int ndestroy = destroy;
            
            if (nx>=0 && ny>=0 && nx<n && ny<m && check[nx][ny][ndestroy]==0) {
                if(v[nx][ny]==1 && ndestroy==0) {
                    ndestroy = 1;
                    check[nx][ny][ndestroy] = 1;
                    q.push({nx, ny, ndist, ndestroy});
                }
                else if(v[nx][ny]==0) {
                    check[nx][ny][ndestroy] = 1;
                    q.push({nx, ny, ndist, ndestroy});
                }
                
            }
        }     
    }

    cout << -1;
    return 0;
}