[백준] 벽 부수고 이동하기 2206번 (c++)

출처 : 2206번: 벽 부수고 이동하기 (acmicpc.net)

2206번: 벽 부수고 이동하기

풀이 방법

처음에는 저번에 풀었던 백준 14502번 연구소가 생각나서 완전탐색 + BFS로 풀려고 했으나

이렇게 풀면 시간 초과가 난다

그래서 벽을 부수는데 greedy한 방법이 있을까 생각 해 봤지만 떠오르지 않아

다른 분들의 풀이를 보니 큐에 추가할때 3차원으로 x, y좌표와 추가적으로 이까지 오면서 벽을 부수었는지 기록해 주었다. 

결국 큐에 추가해주어야 하는 경우는 2가지로 nextX좌표와 nextY좌표가 범위내인지 판별후

1. 위치가 벽이 아닌 길인경우 큐에 추가

2. 위차가 벽이면서 지금 까지 오는 길에 벽을 부수지 않았다면 큐에 x, y,좌표와 벽을 부수었다고 저장

위 두가지 경우인 경우 큐에 넣어주면 된다

#include <bits/stdc++.h>
#define pii pair<pair<int, int>, int>
using namespace std;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int N, M;
int visited[1001][1001][2];
int distance_map[1001][1001][2];
vector<string> board;

int BFS() {
    queue<pii> que;
    que.push(make_pair(make_pair(0, 0), 0));
    distance_map[0][0][0] = 1;

    while (!que.empty()) {
        int y = que.front().first.first;
        int x = que.front().first.second;
        int break_block = que.front().second;        
        que.pop();

        for (int i = 0;i < 4;i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N) {
                if (board[nextY][nextX] == '0') { // 만약 벽이 아닌 경우
                    if (visited[nextY][nextX][break_block] == 0) {
                        visited[nextY][nextX][break_block] = 1;
                        que.push(make_pair(make_pair(nextY, nextX), break_block));
                        distance_map[nextY][nextX][break_block] = distance_map[y][x][break_block] + 1;
                    }
                }
                else { //벽이 있는 경우
                    if(break_block == 0 && visited[nextY][nextX][break_block] == 0 ) {
                        visited[nextY][nextX][break_block] = 1;
                        distance_map[nextY][nextX][1] = distance_map[y][x][break_block] + 1;
                        que.push(make_pair(make_pair(nextY, nextX), 1));
                    }
                } 
                if (nextY == N-1 && nextX == M-1) { // 탈출 조건
                    return distance_map[nextY][nextX][break_block];
                }

            }
        }
    }
    return -1;
}


int main() {
    cin >> N >> M;
    memset(visited, 0, sizeof(visited));
    for (int i = 0;i < N;i++) {
        string st;
        cin >> st;
        board.push_back(st);
    }
    if (N == 1 && M == 1) {
        cout <<1;
        return 0;
    }
    cout << BFS();
    return 0;
}