BOJ 14442, 벽 부수고 이동하기 2
ProblemSolving ·이 문제는 그래프 문제 입니다. 저는 bfs를 이용하였습니다.
풀이
벽 부수고 이동하기 와 굉장히 유사한 문제입니다.
cnt가 최소거리를 구해주는 변수이고 x가 n y가 m에 도달하지 못하고 끝난다면 -1값을 리턴해주면 됩니다.
기본 bfs에서 크게 달라지는 게 없죠? 벽을 부술 기회가 남아있다면 1이여도 지나갈 수 있게 해주면 됩니다.
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int n, m, k;
int chk[1001][1001][11];
int a[1001][1001];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
queue <pair<pair<int, int>, pair<int, int>>> q;
int bfs(int x, int y, int cnt, int ck)
{
chk[x][y][ck] = 1;
q.push({ {x,y},{cnt + 1,ck} });
while (!q.empty())
{
x = q.front().first.first;
y = q.front().first.second;
cnt = q.front().second.first;
ck = q.front().second.second;
q.pop();
if (x == n && y == m) return cnt;
for (int i = 0; i < 4; i++)
{
int xx = x + dx[i];
int yy = y + dy[i];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && chk[xx][yy][ck] == 0)
{
if (a[xx][yy] == 0)
{
chk[xx][yy][ck] = 1;
q.push({ {xx,yy },{cnt + 1,ck} });
}
else if (a[xx][yy] == 1 && ck < k)
{
chk[xx][yy][ck] = 1;
q.push({ {xx,yy },{cnt + 1,ck + 1} });
}
}
}
}
return -1;
}
int main()
{
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%1d", &a[i][j]);
printf("%d", bfs(1, 1, 0, 0));
return 0;
}