BJ2206 벽 부수고 이동하기

풀이

방문여부를 DP로 이용하는 BFS

SWEA의 보급로 문제의 풀이와 약간 유사하면서 다른 점이 있다 https://tbtb7-sw.tistory.com/95

탐색할 때 다음 지점을 탐색할 때 경우의 수를 나눠야 했고 비용을 기록하는 방식이 약간 달랐다.

• 첫 지점을 시작으로 주변 점들을 탐색한다. loop가 한번 돌 때 이동한 거리가 같은 경우의 수가 큐에 모두 담겨있고 각 경우를 모두 확인하고 루프를 계속한다.(한턴한턴 진행하는 것 처럼)

• 현재까지 이동한 거리를 cnt를 이용하여 기억하고 있으며 주변 점을 탐색했을 시 이동 거리를 DP 배열에 기록해둔다.

1. 큐에 있는 탐색할 점의 4방향을 확인한다.

   1. 벽을 부순 적이 있을 때

      벽이 없는 곳만 방문 가능하다.

   2. 벽을 부순 적이 없을 때

      벽이 있든 없든 방문 가능하다.

2. 1-2에서 방문 가능한 경우,

   1. DP 값이 현재 cnt보다 큰 경우, 방문 가능하므로 큐에 푸시한다.

      벽을 부순적이 있는지 없는지를 기록하는 변수(isBroken) 를 함께 푸시한다.

   2. 작다면 현재 방문하는 경우의 수는 답이 될 수 없으므로 제외한다.(푸시하지 않는다.)

   만약 방문 가능한 점이 마지막 점이라면 cnt가 현재 이동한 거리이고 이보다 작은 거리로 도착할 수 없기 때문에 cnt를 리턴하여 출력한다.

   아니라면 1을 반복한다.

3. 큐에 탐색할 점이 없는 경우라면 마지막 점에 도달하지 못한 경우이므로 INF를 리턴하여 불가능한 경우로 간주하여 -1을 출력한다.

이렇게 했을 때 DP를 한개 썼더니 벽을 뚫고 간 경우에 도달한 지점에 벽을 뚫지 않은 경우가 가지 못하는 현상이 발생했다.

그래서 벽을 뚫고 가는 경우와 벽을 뚫지 않고 가는 경우를 따로 기억할 DP 배열을 두개 써서 해결하였다.

DP 배열은 해당 점까지 벽을 부수지 않고 / 부수고 오는 최소비용이 되고 위의 알고리즘에서 이를 반영해서 해결할 수 있었다.

다른 풀이를 보니 그래서 그냥 방문 check 배열을 두개쓰면 해결할 수 있는 것 같은데 그게 왜 모든 경우를 포함할 수 있는 건지 이해가 되지 않고 있다...

이것또한 BFS로 탐색하는 도중에 DP를 활용해서 동일한 탐색을 하지 않는 방법인데 시간복잡도는 어떻게 계산해야 할지 모르겠다.

코드

//! 2020.03.09
// TODO BJ2206_벽부수고이동하기
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

struct myPoint{
    int y;
    int x;
    int isBroken;
};

const int MAX = 1050;
const int INF = 987654321;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
int N,M;
int inMap[MAX][MAX];
queue <myPoint> myQ;
int DP[MAX][MAX][2];

int getMin(int n1,int n2){
    if(n1<n2) return n1;
    else return n2;
}

bool inRange(int y,int x){
    if(y>=0 && y<N && x>=0 && x<M) return true;
    else return false;
}

bool isEnd(int y,int x){
    if(y==N-1 && x==M-1) return true;
    else return false;
}

void initDP(){
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            for(int k=0;k<2;k++) DP[i][j][k] = INF;
        }
    }
}

void print(int k){
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            printf("%d ",DP[i][j][k]);
        }
        printf("\n");
    }
}

int getResult(){
    int cnt = 1;
    myPoint current;
    current.y = 0;
    current.x = 0;
    current.isBroken = 0;
    myQ.push(current);
    DP[current.y][current.x][current.isBroken] = cnt;

    while(!myQ.empty()){
        int qSize = myQ.size();
        cnt++;
        for(int s=0;s<qSize;s++){
            current = myQ.front();
            myQ.pop();
            if(isEnd(current.y,current.x)) return DP[current.y][current.x][current.isBroken];
            for(int dir=0;dir<4;dir++){
                myPoint next;
                next.y = current.y+dy[dir];
                next.x = current.x+dx[dir];
                if(inRange(next.y,next.x)){
                    if(DP[next.y][next.x][current.isBroken]>cnt){
                        if(inMap[next.y][next.x]==0){
                            next.isBroken = current.isBroken;
                            myQ.push(next);
                            DP[next.y][next.x][current.isBroken] = cnt;
                        }else{
                            if(current.isBroken==0){
                                next.isBroken = 1;
                                myQ.push(next);
                                DP[next.y][next.x][current.isBroken] = cnt;
                            }
                        }
                    }
                }
            }
        }
    }
    return INF;
}

int main(){
    // freopen("input.txt", "r", stdin);
    scanf("%d %d",&N,&M);
    for(int i=0;i<N;i++){
        char tmp[MAX];
        scanf("%s",tmp);
        for(int j=0;j<M;j++){
            inMap[i][j] = tmp[j]-'0';
        }
    }
    initDP();
    int result = getResult();
    if(result>=INF) result = -1;
    printf("%d\n",result);
    return 0;
}