[BOJ/2206번벽부수고이동하기] c++ / BFS

문제

(1, 1)칸에서 (N, M)칸까지 가는 최단 경로를 구하는 문제

-벽 하나를 부술 수 있음 

생각

브루트포스로 풀면 N, M이 1000이하의 수여서 시간초과 뜸 

아직 시간복잡도 계산할 줄 몰라서 그냥 풀어서 제출했더니, 시간초과가 아니라 런타임 레어가 떠서 당황함

힘들어서 구글링 해서 방법 찾았음

vis를 3차원 배열로 만들어서 벽을 부수었을 때와 부수지 않았을 때의 방문칸으로 나눠줌

 

문제풀이

1. 일단 bfs 문제랑 똑같음

2. 만약 해당 칸이 벽이라면,

-1) 벽을 부순 적이 있는지 확인

-2) 없을 경우, 큐에 push 해줌 ( vis[][][1] / 0은 벽을 부수지 않았을 때, 1은 벽을 부수었을 때의 방문칸을 나타냄 / B+1 해줌 )

3.만약 해당 칸이 벽이 아니라면

-1) 해당칸의 방문칸의 방문여부를 확인

-2) 방문하지 않았다면, 큐에 push 해줌 ( 2번 과정을 걸쳤다면 vis[][][1], 그렇지 않다면 vis[][][0] 임 / 그래서 그냥 B로 넘겨줌 )

4.반복문 돌다가 (N-1, M-1)칸까지 오면 cnt 출력하고 종료

5.반복문에서 벗어난다면 -1 출력

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define X first
#define Y second
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int board[1001][1001];
int vis[1001][1001][2];
int N, M;
int BFS() {
    queue<pair<pair<int, int>, pair<int, int>>> Q; // i, j, 벽 부순 유무, 경로길이
    Q.push({{0, 0}, {0, 1}});
    vis[0][0][0] = 1;

    while (!Q.empty()) {
        int x = Q.front().X.X;
        int y = Q.front().X.Y;
        int B = Q.front().Y.X;
        int cnt = Q.front().Y.Y;
        Q.pop();

        if ( x == N-1 && y == M-1 )
            return cnt;
        for ( int dir = 0; dir < 4; dir++ ) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if ( nx < 0 || nx >= N || ny < 0 || ny >= M ) continue;
            
            if ( board[nx][ny] == 1 && B == 0 ) { // 벽칸이고, 벽을 부순 적이 없다면
                vis[nx][ny][1] = 1;
                Q.push({{nx, ny}, {B+1, cnt+1}});
            }
            else if ( board[nx][ny] == 0 && vis[nx][ny][B] == 0 ) { // 이동가능한 칸이고, 방문한 적이 없다면
                vis[nx][ny][B] = 1;
                Q.push({{nx, ny}, {B, cnt+1}});
            }
        }
    }
    return -1;
} 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    for ( int i = 0; i < N; i++ ) {
        string str;
        cin >> str;
        for ( int j = 0; j < M; j++ ) {
            int tmp = str[j] - '0';
            board[i][j] = tmp;
        }
    }

    cout << BFS();
}