BOJ 2206 : 벽 부수고 이동하기

풀이 요약

BFS() 응용 문제.

풀이 상세

1. 입력 값을 받는다.

2. 이 문제는 벽을 부수는 경우와, 벽을 부수지 않고 가는 경우를 따로 따로 방문처리를 해야한다.

   • 처음에는 벽을 부술 수 있는 상태만 관리하여 진행하면 된다고 생각했다.

   • 하지만 이러한 경우, 벽을 부수고 접근하는 거나 안 부수고 돌아서 접근이 모두 가능한 좌표가 있는 경우, 이미 방문처리가 되어버려, 둘 중 하나의 방법으로만 접근이 가능하게 된다.

   • 따라서 3차원 방문처리를 통해, 벽을 부수고 접근하는 경우와 부수지 않고 접근하는 경우를 분리하여 체크해야한다.

#include <iostream>
#include <queue>
using namespace std;
int N, M, maps[1004][1004];
bool visited[1004][1004][2];
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, -1, 0, 1};

struct Node {
    int r, c, dist;
    bool crush;
};

void input() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    string str;
    for (int i = 0; i < N; i++) {
        cin >> str;
        for (int j = 0; j < M; j++) {
            maps[i][j] = str[j] - '0';
        }
    }
}

int bfs() {
    queue<Node> q;
    q.push({0, 0, 1, false});
    visited[0][0][0] = true;
    while (!q.empty()) {
        Node curr = q.front();
        q.pop();

        if (curr.r == N - 1 && curr.c == M - 1) {
            return curr.dist;
        }

        for (int d = 0; d < 4; d++) {
            int nr = curr.r + dr[d];
            int nc = curr.c + dc[d];

            if (nr < 0 || nc < 0 || nr >= N || nc >= M)
                continue;

            if (visited[nr][nc][0] && visited[nr][nc][1])
                continue;

            if (maps[nr][nc] == 0) {
                if (!curr.crush && !visited[nr][nc][0]) {
                    visited[nr][nc][0] = true;
                    q.push({nr, nc, curr.dist + 1, curr.crush});
                } else if (curr.crush && !visited[nr][nc][1]) {
                    visited[nr][nc][1] = true;
                    q.push({nr, nc, curr.dist + 1, curr.crush});
                }
            } else if (maps[nr][nc] == 1) {
                if (!curr.crush) {
                    visited[nr][nc][1] = true;
                    q.push({nr, nc, curr.dist + 1, true});
                }
            }
        }
    }

    return -1;
}

int main() {
    input();
    cout << bfs();
    return 0;
}