[백준/C,C++] 2206번: 벽 부수고 이동하기

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

풀이

개인적으로 BFS 기초를 공부하며 가장 어려웠던 문제인데,

 

관건은 벽을 부수고 도달한 최소 거리, 벽을 부수지 않고 도달한 최소 거리 모두를 기록하는 것입니다.

 

해당 부분을 다른 분들의 아이디어를 보고 해결하였습니다.

 

bool 변수를 3차원으로 두는 것인데, 마지막에 [y][x][2] 의 3차원 형태로 구현함으로써

 

벽을 부수고 도달한 최소 거리, 벽을 부수지 않고 도달한 최소 거리 모두를 기록할 수 있게 됩니다.

 

#include<iostream>
#include<queue>

using namespace std;

const int MAX = 1000;
const int INF = 1000000;

int n, m;
string arr[MAX];
bool visited[MAX][MAX][2];
struct Map {
    int y, x, cnt;
    bool chance;
    bool check() {
        if (y >= 0 && x >= 0 && y < n && x < m) {
            if (!visited[y][x][chance]) {
                if (arr[y][x] == '0') return true;
                else if (arr[y][x] == '1' && !chance) return true;
            }
        }
        return false;
    }
};
queue<Map> q;
int direction[4][2] = {
    {1, 0}, {0, 1}, {-1, 0}, {0, -1}
};

int BFS()
{
    int res = INF;
    if (n == 1 && m == 1) return 1;
    q.push({ 0, 0, 1, false });
    visited[0][0][0] = true;
    while (!q.empty()) {
        Map node = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = node.y + direction[i][0];
            int nx = node.x + direction[i][1];
            Map next = { ny, nx, node.cnt + 1, node.chance };
            if (next.check()) {
                if (arr[ny][nx] == '1') next.chance = true;
                q.push(next);
                visited[ny][nx][next.chance] = true;
                if (ny == n - 1 && nx == m - 1) res = min(res, next.cnt);
            }
        }
    }
    return res;
}

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

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int res = BFS();
    if (res != INF) cout << res;
    else cout << -1;

    return 0;
}

반례

Input

1 1

1

Output

1

 

Input

5 4
0000
1110
0000
1111
0000

Output

8