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

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

정말 고민을 많이 한 문제였는데.. 접근방식이 계속 틀린 것이 문제였다...

 

BFS에 다가 자신의 상태를 저장을 해주어야 하는데 그 생각을 못하고 시작점과 끝점에서 BFS를 두번돌려서 만나는 지점이 같으면 벽을 부수는 걸로 접근을 했었다.

 

답지를 보기 싫었는데 결국 보게 되서 좀 아쉬운 문제였고 아직 멀었구나 느꼈다..

 

참고 블로그: rebas.kr/658

BOJ 2206 · 벽 부수고 이동하기

이 블로그의 해답이 제일 깔끔하고 이해가 잘되었다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
using namespace std;

struct map {
    int x, y, w;
};

int n, m;
int a[1001][1001];
int dist[1001][1001][2];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };

int bfs() {
    queue<map> q;
    q.push({ 0, 0, 0 });
    dist[0][0][0] = 1;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int w = q.front().w;
        q.pop();
        if (x == n - 1 && y == m - 1) {
            return dist[x][y][w];
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (dist[nx][ny][w]) continue;
            if (a[nx][ny] == 0) {
                dist[nx][ny][w] = dist[x][y][w] + 1;
                q.push({ nx, ny, w });
            }
            if (a[nx][ny] == 1 && w == 0) {
                dist[nx][ny][1] = dist[x][y][w] + 1;
                q.push({ nx, ny, 1 });
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &a[i][j]);
        }
    }
    printf("%d", bfs());
    return 0;
}