(C++) [백준 14442번] 벽 부수고 이동하기 2

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

14442번: 벽 부수고 이동하기 2

https://www.acmicpc.net/problem/1600 문제와 거의 유사한 문제인 것 같다.

https://www.acmicpc.net/problem/2206 문제에서는 벽을 1개만 부술 수 있었는데, 이 문제는 벽을 k개 부술 수 있다.

 

https://pl-are.tistory.com/26 에서 풀었던 방법처럼, 3차원 배열을 k개만큼 선언해서 벽을 부술 때 마다 인덱스를 1씩

증가시켜주면 된다.

 

내가 생각한 방법은 다음과 같다.

1. x,y까지 오는데 벽 0개 부순 최단거리를 board[x][y][0]에 저장했다고 한다면, 벽을 1개 부순 최단거리는 board[x][y][1]에 있을거고, k개 부순 최단거리는 board[x][y][k]에 저장되어 있을 것이다. 따라서 벽을 부술수 있는지 보고 현재 부순 벽이 k개보다 작고, 다음 갈 지점이 벽이며, 아직 방문하지 않았다면 큐에 추가하고 거리를 1 추가하면 된다. 벽이 아닌 경우에는 그냥 추가하면 된다.

2. 현재 위치가 n-1,m-1이라면 dist의 현재 위치에 해당하는 값을 리턴하면 된다.

 

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
#define MAX 1002
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int board[MAX][MAX];
int dist[MAX][MAX][11]; // [0] = 벽을 부수지 않은 최단거리, [1~k] = 벽을 i개 부순 최단거리
int n, m, k;
queue <tuple<int, int, int>> q;
void input()
{
	cin >> n >> m >> k;
	char c;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> c;
			board[i][j] = c - '0';
		}
	}
}
int solve()
{
	q.push({ 0,0,0 });
	dist[0][0][0] = 1; // 초기 설정
	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		int x, y, broken;
		tie(x, y, broken) = cur;
		if (x == n - 1 && y == m - 1) return dist[x][y][broken];

		for (int dir = 0; dir < 4; dir++)
		{
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (broken < k)
			{
				if (board[nx][ny] == 1 && dist[nx][ny][broken + 1] == 0) // 벽이 있고,부술 수 있음
				{
					dist[nx][ny][broken+1] = dist[x][y][broken] + 1;
					q.push({ nx,ny,broken + 1 });
				}
			}
			if (board[nx][ny] == 0 && dist[nx][ny][broken] == 0) // 벽은 없지만 갈 수 있는 길
			{
				dist[nx][ny][broken] = dist[x][y][broken] + 1;
				q.push({ nx,ny,broken });
			}
		}
	}
	return -1;
}
int main()
{
	cin.tie(0); ios::sync_with_stdio(0);
	input(); cout << solve();
}