[Algo] 백준 벽부수고 이동하기 c++ // 최단거리는 bfs 3차원

* 2차원이 안되는 이유

• 처음설계 
  • 상태 : (y, x , 그때 벽부순 count)를 두고 bfs를 돌리기
  • if(next_cnt >= 2) continue;

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct A {
    
    int y;
    int x;
    int cnt; // 여기좌표에 올때까지 부신 벽의갯수

    A(int y, int x, int cnt) : y(y), x(x), cnt(cnt) {};
};

int n, m, arr[1004][1004], vis[1004][1004];
int dy[] = { 1,0,-1,0 };
int dx[] = { 0,1,0,-1 };
ll ret; //배정된 예산중 최대값
queue<A> q;



int main()
{
    cin >> n>>m;

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

    /*for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << arr[i][j];
        }cout << "\n";
    }*/

    vis[0][0] = 1;
    q.push(A(0,0,0));
    while (q.size()) {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        //cout << y << " " << x << " " << cnt << "\n";
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            int nc = cnt;
            if (ny >= n || ny < 0 || nx >= m || nx < 0) continue;
            if (vis[ny][nx]) continue;
            
            if (arr[ny][nx] == 1) nc++;
            if (nc >= 2) continue;

            q.push(A(ny,nx, nc));
            vis[ny][nx] = vis[y][x] + 1;
        }
    }

    /*cout << "\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << vis[i][j];
        }cout << "\n";
    }*/

    if (vis[n - 1][m - 1] == 0) {
        cout << -1;
        return 0;
    }
    cout << vis[n - 1][m - 1];

    return 0;
}

• 반례
•  

반례와 그때의 vis

사람의 의도 vs 실제 / 1번경로와 2번경로가 겹친다. / 2번 경로때문에 1번경로가 더이상 진행되지 않는다.

• 1번경로는 벽은 부수지않는상태이다.
• 2번경로는 벽하나를 부수는 상태이다.
• 벽을 부수는 상태가 벽은 부수지않는 상태에 영향을 준다.
• 1번의 상태는 벽을 하나도 안부순상태
• 2번은 벽을 하나깨고 온 상태
• 이를 격리해야한다.
• 즉, 매 좌표마다 벽을 깻는지 안깻는지 기록하고 구분해야 한다.

 

* 해결방안 : 상태추가

• 벽을 꺳는지 안깻는지 상태를 추가하면된다.
• vis [ y ] [x] [crashed]
• 큐에도 똑같은 상태를 넣어준다. 
• 아래와 같이 상태를 완전히 분리한다. (vis)

각각의 상태일때 vis 배열값

• crashed=1인 상태에서는 1을 만난경우, 진행을 못한다.
• crashed=0인 상태에서는 1을 만난경우, 상태를 바꾼다(옆세계로 넘어감)
• 키포인트 : crashed=0에서 crashed=1 쪽으로만 넘어갈수 있음!!! (by 문제조건)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

//상태정의 : (y, x, 벽부쉇는지)
struct A {
    
    int y;
    int x;
    int crashed; // 현재 상태일때 벽부쉇는지

    A(int y, int x, int crashed) : y(y), x(x), crashed(crashed) {};
};

int n, m, arr[1004][1004], vis[1004][1004][2];
int dy[] = { 1,0,-1,0 };
int dx[] = { 0,1,0,-1 };
ll ret; //배정된 예산중 최대값
queue<A> q;



int main()
{
    cin >> n>>m;

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

    /*for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << arr[i][j];
        }cout << "\n";
    }*/

    int ok = 0; //갈수있는지
    vis[0][0][0] = 1;
    q.push(A(0,0,0));
    while (q.size()) {
        int y = q.front().y;
        int x = q.front().x;
        int crashed = q.front().crashed;
        //cout << y << " " << x << " " << crashed << "\n";
        q.pop();
        //탈출은 pop 다음에
        if (y == n - 1 && x == m-1) {
            ok = 1;
            ret= vis[y][x][crashed];
            break;
        }

        for (int i = 0; i < 4; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny >= n || ny < 0 || nx >= m || nx < 0) continue;
            if (vis[ny][nx][crashed]) continue;
            
            //next가 벽이 아닌경우, 그냥 bfs와 동일논리
            if (arr[ny][nx] == 0) {
                vis[ny][nx][crashed] = vis[y][x][crashed] + 1;
                q.push(A(ny, nx, crashed));
            }
            else { //next가 벽인경우
                if (crashed == 1) continue; //이미 부셧다면 불가.

                //안부신경우(crashed==0), 다음상태는 부순걸로표시
                vis[ny][nx][crashed+1] = vis[y][x][crashed] + 1;
                q.push(A(ny, nx, crashed+1));
            }
        }
    }

    if (ok) {
        cout << ret;
    }
    else
        cout << -1;
    //cout << "\n";
    //for (int i = 0; i < n; ++i) {
    //    for (int j = 0; j < m; ++j) {
    //        cout << vis[i][j]<< " ";
    //    }cout << "\n";
    //}

    //if (vis[n - 1][m - 1] == 0) {
    //    cout << -1;
    //    return 0;
    //}
    //cout << vis[n - 1][m - 1];

    return 0;
}

 

* 행동영역

• 최단거리는 bfs
• 조건이 추가되면, 상태로 나타낸다.
• 각각의 상태를 분리시키고 설계한다.
• 상태를 vis, queue에 넣는다.
• 탈출조건을 pop 직후에두고, flag를 둬서 못가는경우를 고려한다.
• struct 사용법 암기.

struct A{
	int a,b,c;
    A(int a, int b, int c) : a(a), b(b), c(c) {}
}

//사용시
A a = A(1,2,3)