백준 2206 벽 부수고

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

이 문제는 일반적인 BFS 검색 문제와 크게 다르지 않으나 벽(1)을 한 번만 이동할 수 있다는 조건에서 큰 차이가 있습니다. 그리고 그 조건은 조금 더 어렵게 만들었습니다.

입력을 2D 배열로 가져오고 찾고자 하는 최단 경로를 3D 배열로 만들어서 해결했습니다. 벽을 부수는 것이 최단 경로일 수 있고, 벽을 부수지 않는 것이 최단 경로일 수 있기 때문입니다.

d(x)(y)(z) = x 행 y 열 z(부서진 벽의 수)로 볼 수 있습니다.

따라서 기존 BFS 검색에서 벽을 허무는 조건을 추가할 수 있습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int a(1001)(1001);    // 입력
int d(1001)(1001)(2); // d(x)(y)(z) : x,y (행, 열), z (벽을 부순 횟수)
int mov(4)(2) = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// 빈칸 -> 빈칸 (ok), 빈 칸 -> 벽 (가능할 수 있다.), 벽 -> 빈 칸(항상), 벽->벽(x, 벽을 한번만 부술 시 있기 때문이다.)
// 정점 (r, c(위치), k(벽을 부순 횟수))
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        string input;
        cin >> input;
        for (int j = 0; j < m; j++)
        {
            a(i)(j) = input(j) - '0';
        }
    }
    queue<tuple<int, int, int>> q;
    d(0)(0)(0) = 1;
    q.push(make_tuple(0, 0, 0));
    while (!q.empty())
    {
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int z = get<2>(q.front());
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int r = x + mov(i)(0);
            int c = y + mov(i)(1);
            if (r >= 0 && r < n && c >= 0 && c < m)
            {
                if (a(r)(c) == 0 && d(r)(c)(z) == 0)
                {
                    d(r)(c)(z) = d(x)(y)(z) + 1;
                    q.push(make_tuple(r, c, z));
                }
                // 벽을 부술 경우
                if (z == 0 && a(r)(c) == 1 && d(r)(c)(z + 1) == 0)
                {
                    d(r)(c)(z + 1) = d(x)(y)(z) + 1;
                    q.push(make_tuple(r, c, z + 1));
                }
            }
        }
    }
    if (d(n - 1)(m - 1)(0) != 0 && d(n - 1)(m - 1)(1) != 0)
    {
        cout << min(d(n - 1)(m - 1)(0), d(n - 1)(m - 1)(1));
    }
    else if (d(n - 1)(m - 1)(0) != 0)
    {
        cout << d(n - 1)(m - 1)(0);
    }
    else if (d(n - 1)(m - 1)(1) != 0)
    {
        cout << d(n - 1)(m - 1)(1);
    }
    else
    {
        cout << -1;
    }
}

d(n-1)(m-1)(0): 벽을 뚫지 않고 n행 m열로 이동

d(n-1)(m-1)(1): 행 n과 열 m에 도달하려면 벽을 한 번 부수고 이동합니다.