2206 벽 부수고 이동하기

2206 벽 부수고 이동하기 (c++)

문제

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

접근 방식

Graph, BFS

1. 기존의 0,0 에서 N,M까지의 벽이 있는 최단거리 문제에서 벽 1개를 부술 수 있는 경우가 추가되었다.
2. 벽을 부수지 않은 cost[0]와 벽을 하나 부순 cost[1]을 가지고 풀면 해결된다.

문제 풀이

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#define INF 987654321
using namespace std;
inline int Min(int a, int b) { return a < b ? a : b; }
int N, M, nowY, nowX, nextY, nextX, answer = INF;
vector<string> board;
int dy[4] = { 0, 0, -1, 1 };
int dx[4] = { -1, 1, 0, 0 };
bool isNew;
void BFS()
{
    vector<vector<int>> cost[2];
    cost[0] = vector<vector<int>>(N, vector<int>(M, INF));
    cost[1] = vector<vector<int>>(N, vector<int>(M, INF));
    cost[0][0][0] = 1;
    cost[1][0][0] = 1;
    queue<pair<int, int>> q;
    q.push({ 0,0 });
    while (!q.empty())
    {
        pair<int, int> now = q.front(); q.pop();
        nowY = now.first;
        nowX = now.second;
        for (int i = 0; i < 4; ++i)
        {
            nextY = nowY + dy[i];
            nextX = nowX + dx[i];
            if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M) continue;
            
            if (board[nextY][nextX] == '1')
            {
                // 벽을 부수기 때문에 cost[0]에서 cost[1]로 비교
                if (cost[1][nextY][nextX] > cost[0][nowY][nowX] + 1)
                {
                    cost[1][nextY][nextX] = cost[0][nowY][nowX] + 1;
                    q.push({ nextY, nextX });
                }
            }
            else
            {
                // 벽을 부수지 않기 때문에 cost[0]과 cost[1]을 각각 비교
                isNew = false;
                if (cost[0][nextY][nextX] > cost[0][nowY][nowX] + 1)
                {
                    cost[0][nextY][nextX] = cost[0][nowY][nowX] + 1;
                    isNew = true;
                }
                if (cost[1][nextY][nextX] > cost[1][nowY][nowX] + 1)
                {
                    cost[1][nextY][nextX] = cost[1][nowY][nowX] + 1;
                    isNew = true;
                }
                // 최신화된 값이 있는 경우 푸쉬
                if (isNew) q.push({ nextY, nextX });
            }
        }
    }

    // 벽을 부순 경우와 부수지 않은 경우 중 최소값을 답으로 취한다.
    answer = Min(cost[0][N-1][M-1], cost[1][N-1][M-1]);
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    if (N == M && M == 1)
    {
        cout << "1\n";
        return 0;
    }
    board = vector<string>(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> board[i];
    }

    BFS();

    if (answer == INF) cout << "-1\n";
    else cout << answer << '\n';

    return 0;
}

다시 생각해 볼 점

1. 벽을 하나만 부실 수 있다고 해서, 벽을 백트래킹으로 하나씩 부셔서 BFS를 진행해보려고 했는데 시간초과가 떴다.
2. 다른 사람의 접근법을 보니 벽을 BFS를 탐색할 때 벽을 부수는 경우까지 고려한다고 하여 처음엔 Breakable이라는 배열로 해당 칸에서 이동 시 벽을 부술 수 있는지 체크했다.
3. 위의 코드로도 성공은 했으나 시간이 오래걸렸다. 다른 방법이 있나 생각해보니 애초에 cost를 벽을 부순 경우와 부수지 않은 경우로 나누고, 벽이 있으면 [0]->[1]로 비교, 벽이 아니면 [0]과 [1]을 각각 비교하면 해결되었다.