[C++] 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

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

    int n, m;
    cin >> n >> m;
    vector<vector<bool>> g(n, vector<bool>(m));
    vector<vector<bool>> chk(n, vector<bool>(m, 0));

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            g[i][j] = (s[j] == '1');
        }
    }

    queue<vector<int>> q;
    // {x index, y index, didBreak, count}
    q.push({0, 0, 0, 1});
    chk[0][0] = true;
    int ans = -1;
    while (!q.empty()) {
        int curi = q.front()[0];
        int curj = q.front()[1];
        int didBreak = q.front()[2];
        int cnt = q.front()[3];
        if (curi == n - 1 && curj == m - 1) {
            ans = cnt;
            break;
        }
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nxti = curi + dx[k];
            int nxtj = curj + dy[k];
            if (nxti >= 0 && nxti < n && nxtj >= 0 && nxtj < m && !chk[nxti][nxtj]) {
                if (!g[nxti][nxtj]) { // 0
                    q.push({nxti, nxtj, didBreak, cnt + 1});
                    chk[nxti][nxtj] = true;
                } else if (g[nxti][nxtj] && didBreak == 0) { // 1
                    q.push({nxti, nxtj, didBreak + 1, cnt + 1});
                    chk[nxti][nxtj] = true;
                }
            }
        }
    }

    cout << ans << '\n';
}

처음에 이렇게 코드를 짰다. 예제는 정상적으로 출력되는데 15% 쯤에서 틀렸습니다가 나왔다. (WA)

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

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

    int n, m;
    cin >> n >> m;
    vector<vector<bool>> g(n, vector<bool>(m));
    vector<vector<vector<bool>>> chk(n, vector<vector<bool>>(m, vector<bool>(2, 0)));

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            g[i][j] = (s[j] == '1');
        }
    }

    queue<vector<int>> q;
    // {x index, y index, didBreak, count}
    q.push({0, 0, 0, 1});
    chk[0][0][0] = true;
    int ans = -1;
    while (!q.empty()) {
        int curi = q.front()[0];
        int curj = q.front()[1];
        int didBreak = q.front()[2];
        int cnt = q.front()[3];
        if (curi == n - 1 && curj == m - 1) {
            ans = cnt;
            break;
        }
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nxti = curi + dx[k];
            int nxtj = curj + dy[k];
            if (nxti >= 0 && nxti < n && nxtj >= 0 && nxtj < m) {
                if (!g[nxti][nxtj] && !chk[nxti][nxtj][didBreak]) { // 0
                    q.push({nxti, nxtj, didBreak, cnt + 1});
                    chk[nxti][nxtj][didBreak] = true;
                } else if (g[nxti][nxtj] && didBreak == 0 && !chk[nxti][nxtj][didBreak + 1]) { // 1
                    q.push({nxti, nxtj, didBreak + 1, cnt + 1});
                    chk[nxti][nxtj][didBreak + 1] = true;
                }
            }
        }
    }

    cout << ans << '\n';
}

문제점

- 방문 체크(chk) 배열이 단일 구조로 되어 있어, 벽을 부순 경로와 부수지 않은 경로를 구분하지 않음.

- 결과적으로, 벽을 부수지 않고 도달할 수 있는 더 유리한 경로가 무시되거나, 잘못된 최단 경로가 계산될 수 있음.

수정 사항

- chk 배열을 3차원으로 확장: chk[n][m][2]로 선언하여 벽을 부수지 않은 경우(didBreak = 0)와 부순 경우(didBreak = 1)를 구분.

- 조건문 수정:
    - 벽이 없는 경우: chk[nxti][nxtj][didBreak]로 방문 여부 체크.
    - 벽이 있는 경우: 벽을 부수지 않았을 때만(didBreak == 0) chk[nxti][nxtj][1]로 방문 처리.

수정해야 하는 이유

- 벽을 부순 경로와 부수지 않은 경로는 다른 경로로 취급해야 하므로 각각 독립적으로 방문 여부를 기록해야 함.

- 벽을 부수지 않고 도달한 경로는 여전히 벽을 부술 기회를 남겨두고 있어 더 유리한 경로 탐색이 가능하므로, 이를 구분하지 않으면 정확한 최단 경로를 계산할 수 없음.

(AC)