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

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

16933번: 벽 부수고 이동하기 3

벽 부수고 이동하기 1,2번에 이어 3번이다. 

1번이 벽을 1개만 부술 수 있었고, 2번은 벽을 K(1<=K<=10)개 부술 수 있었다면 3번은 벽을 K(1<=K<=10)개 부술 수 있지만 낮에만 벽을 부술 수 있다는 조건이 추가된 문제이다.

한 번 이동할 때마다 낮과 밤이 바뀌고, 밤에는 벽을 부술 수 없다. 제자리에서 한 번 움직이는 것도 가능하며 이 때는 이동 횟수가 1 추가된다.

다른 벽 부수고 이동하기 문제들처럼 벽을 K번 이내로 부수면서 (n-1,m-1)까지 가는 최단 거리를 출력하면 된다.

 

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

1. 이동하는 경우를 3가지로 나눈다.

1-1. 벽을 부술 수 있는 경우: 내가 이때까지 벽을 부순 횟수가 k보다 작고, 현재 시간이 낮이고, 다음으로 이동할 곳이 벽인 경우

1-2. 벽을 부술 수 없는 경우: 다음으로 이동할 곳이 벽인데 밤인 경우

1-3. 벽을 부수지 않아도 되는 경우: 다음으로 이동할 곳이 벽이 아닌 경우

2. BFS를 수행하며 1번의 3가지를 각각 검사한다.

3. 내가 현재 있는 곳이 (n-1,m-1)이라면 (n-1,m-1)에 있는 값을 출력하면 된다. 만약 큐가 빌 때 까지 (n-1,m-1)에 도착하지 못한다면 -1을 리턴하면 된다.

이렇게 3가지로 나누어서 각각에 대해 코드를 구현하면 된다.

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
#define MAX 1002
#define KMAX 12
int board[MAX][MAX];
int dist[MAX][MAX][KMAX][2];
queue <tuple<int, int, int, int>> q;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n, m, k;
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,true });
	dist[0][0][0][true] = 1;
	while (!q.empty())
	{
		int x, y, broken;
		bool day;
		tie(x, y, broken, day) = q.front(); q.pop();
		if (x == n - 1 && y == m - 1) return dist[x][y][broken][day];

		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] && day && !dist[nx][ny][broken+1][!day])
				{
					dist[nx][ny][broken + 1][!day] = dist[x][y][broken][day] + 1;
					q.push({ nx,ny,broken + 1,!day });
				}
				
			}
			if (board[nx][ny] && !day && !dist[nx][ny][broken][!day])
			{
				dist[x][y][broken][!day] = dist[x][y][broken][day] + 1;
				q.push({ x,y,broken,!day });
			}
			if (!board[nx][ny] && !dist[nx][ny][broken][!day])
			{
				dist[nx][ny][broken][!day] = dist[x][y][broken][day] + 1;
				q.push({ nx,ny,broken,!day });
			}
		}
	}
	return -1;
}
int main()
{
	cin.tie(0); ios::sync_with_stdio(0);
	input();
	cout << solve();
}