[BOJ / C++] 벽 부수고 이동하기 (BFS로 풀이, 완전탐색 X)

문제링크: https://www.acmicpc.net/problem/2206

 

1. 잘못된 풀이 (완전탐색 + Pruning)

1-1. 코드

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> board(n, vector<int>(m, 0));
    vector<vector<int>> dist(n, vector<int>(m, -1));

    vector<pair<int, int>> breakPoint;
   
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < m; j++) {
            board[i][j] = str[j] - '0';
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j > 0 && j < m-1) {
                if (board[i][j-1] == 0 && board[i][j] == 1 && board[i][j+1] == 0) breakPoint.push_back({i, j});
            }
            if (i > 0 && i < n-1) {
                if (board[i-1][j] == 0 && board[i][j] == 1 && board[i+1][j] == 0) breakPoint.push_back({i, j});
            }
        }
    }

    int mn = 1e9;

    queue<pair<int, int>> Q;
    Q.push({0, 0});
    dist[0][0] = 1;
    
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        int x = cur.first;
        int y = cur.second;
        
        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 || dist[nx][ny] >= 1) continue;
            
            Q.push({nx, ny});
            dist[nx][ny] = dist[x][y] + 1;
        }
    }
    if (dist[n-1][m-1] != -1) mn = min(mn, dist[n-1][m-1]);


    for (auto bp: breakPoint) {
        int x = bp.first; 
        int y = bp.second;

        vector<vector<int>> bpBoard(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                bpBoard[i][j] = board[i][j];
            }
        }
        bpBoard[x][y] = 0;

        vector<vector<int>> bpDist(n, vector<int>(m, -1));

        queue<pair<int, int>> Q;
        Q.push({0, 0});
        bpDist[0][0] = 1;

        while (!Q.empty()) {
            auto cur = Q.front(); Q.pop();
            int x = cur.first;
            int y = cur.second;
            
            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 (bpBoard[nx][ny] == 1 || bpDist[nx][ny] >= 1) continue;
                
                Q.push({nx, ny});
                bpDist[nx][ny] = bpDist[x][y] + 1;
            }
        }
        if (bpDist[n-1][m-1] != -1) mn = min(mn, bpDist[n-1][m-1]);
    }
    

    if (mn == 1e9) mn = -1;
    cout << mn;
}

 

1-2. 틀린 이유 분석

시간제한이 2초이길래 완전탐색 + Pruning 해도 되나부다하고 그냥 막 풀고나서 시간초과 판정을 받았다.. 시간복잡도를 좀 더 신경쓰자.. 가로로 010 또는 세로로 010인 좌표들을 조사해서 breakPoint 배열에 가지고 있다가 하나씩 꺼내서 해당 부분 블럭을 0으로 뿌셔서 모두 BFS를 돌면서 최솟값을 찾아냈다.

이 경우 시간복잡도는 O(bp개수 * n * m)이 되는데 bp개수는 최대 n * m에 근사되므로 O(n^2 * m^2)이고, n, m은 최대 1000이므로 10^12 > 10^8으로 시간초과가 된다.

그렇다면 각 경우에 대해 BFS를 모두 돌면 안된다는 소리이다. 어떻게 해야할까?

 

 

2. 올바른 풀이

1. 코드

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> board(n, vector<int>(m, 0));
    vector<vector<vector<int>>> dist(n, vector<vector<int>>(m, vector<int>(2, -1)));
   
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < m; j++) {
            board[i][j] = str[j] - '0';
        }
    }

    queue<tuple<int, int, int>> Q;
    Q.push({0, 0, 0});
    dist[0][0][0] = 1;
    
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        int x, y, broken;
        tie(x, y, broken) = cur;
        
        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;

            // {nx, ny}가 빈칸이고 방문한적이 없으면, 같은 broken 상태에서 이동
            if (board[nx][ny] == 0 && dist[nx][ny][broken] == -1) {
                Q.push({nx, ny, broken});
                dist[nx][ny][broken] = dist[x][y][broken] + 1;
            }
            
            // {nx, ny}를 부수는 경우
            if (board[nx][ny] == 1 && !broken && dist[nx][ny][1] == -1) {
                Q.push({nx, ny, 1});
                dist[nx][ny][1] = dist[x][y][0] + 1;
            }
        }
    }

    int dist0 = dist[n-1][m-1][0];
    int dist1 = dist[n-1][m-1][1];
    
    int ans = -1;
    if (dist0 != -1 && dist1 != -1) ans = min(dist0, dist1);
    else if (dist0 == -1) ans = dist1;
    else if (dist1 == -1) ans = dist0;

    cout << ans;
}

 

2. 분석

dist 배열을 3차원으로 만들어서 벽을 부쉈는지 여부를 가지고 다닌다. dist[x][y][broken]으로 사용하고 broken==0이면 아직 한번도 부수지 않고 {x, y}까지 온 것이고, broken==1이면 한번 부수고 {x, y}까지 온 상황임을 나타낸다. 이렇게 dist 배열을 활용하면 한번의 BFS로 해결할 수 있다. 

 

얼핏 생각하면 굉장히 헷갈린다. 그런데 먼저 벽을 뚫고 [1]에 들어온다고 해도 board[nx][ny] == 0인 곳만 이동할 수 있도록 제한을 둬놨으므로 이런 걱정은 하지 않아도 된다. 이해를 돕기 위해 테스트케이스에는 없는 예시를 보자. 이 테스트 케이스를 보면 좀 직관적으로 이해하기 쉽다.

// input board
6 4
0000
1110
1000
0000
0111
0000

// dist[x][y][0]
1 2 3 4 
-1 -1 -1 5 
-1 8 7 6 
10 9 8 7 
11 -1 -1 -1 
12 13 14 15 

// dist[x][y][1]
3 4 5 6 
2 3 4 5 
9 4 5 6 
6 5 6 7 
7 10 9 8 
8 9 10 9

 

 

3. 시간복잡도

한번의 BFS로 돌은 덕분에 시간복잡도는 O(2 * n * m)이 되고 2 * 1000 * 1000 = 10^6 < 10^8으로 시간내 통과가 가능하다.