https://www.acmicpc.net/problem/2206
#2206 벽을 부수고 움직여라
N×M 행렬로 표현되는 지도가 있습니다.
지도에서 0은 이동할 수 있는 위치를 나타내고 1은 이동할 수 없는 벽이 있는 위치를 나타냅니다.
(1, 1)에서 (N, M) 위치로 이동하려고 합니다.
이것이 최단 경로입니다.
www.acmicpc.net
이 문제는 일반적인 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에 도달하려면 벽을 한 번 부수고 이동합니다.