Boj 16933) 벽 부수고 이동하기 3

문제

백준 16933

설명

1. 각 위치에 대한 방문체크만 하면 틀린다. 같은 위치라도 남은 폭탄의 갯수에 따라 다른 결과를 얻을 수 있기 때문이다. 그러므로 방문 시 폭탄의 여부를 체크해서 더 많은 폭탄을 가지고 있을 때만 같은 위치에 중복으로 갈 수 있게 한다. 예를들어 int visitTB[1000][1000] 이런식으로 구성할 수 있겠다. 방문 체크 시 남은 폭탄에 해당하는 차원을 추가해 bool visitTB[1000][1000][11] 이런식으로 처리할 수도 있지만, 이 경우는 모든 경우를 계산하게 되어 느리다.

2. 낮에는 쉴 필요가 없다. 그러므로 낮 밤 모두 쉬는걸 넣지 말자.

3. 방문체크용 배열을 따로 만들기에는 공간이 너무 아까웠다. 그래서 board[] 의 맨 앞비트만 0, 1 여부를 사용하고, 나머지 비트는 방문 시 가진 폭탄의 최태갯수를 넣었다.

시간 복잡도

O(\(\mathrm{N}\mathrm{M}\mathrm{K}\))

코드

int w, h, k;
unsigned char board[1001 * 1001];
int dx[]{ -1, 1, 0, 0 }, dy[]{ 0, 0, 1, -1 };

struct E {
	E(int pos, int nBomb) : pos(pos), nBomb(nBomb) {}
	int pos;
	int nBomb = 0;
};

int main()
{
	fastio;
	cin >> h >> w >> k;
	for (int i = 0; i < w*h; i++)
	{
		char tmp;
		cin >> tmp;
		board[i] = tmp - '0';
	}

	int nMove = 0;
	queue<E> q; 
	q.push(E(0, k));
	
	while (!q.empty())
	{
		int size = q.size();
		bool day = (++nMove % 2);
		for (int i = 0; i < size; i++)
		{
			auto tmp = q.front(); q.pop();
	
			if (tmp.pos == w * h - 1) {
				cout << nMove;
				return 0;
			}
	
			int cur_x = tmp.pos % w, cur_y = tmp.pos / w;
			for (int j = 0; j < 4; j++)
			{
				int x = cur_x + dx[j], y = cur_y + dy[j], d = y * w + x;
				if (x < 0 || y < 0 || x >= w || y >= h) continue;
	
				// board => [leftBomb+1][isOne] 이므로 맨 앞비트를 제거 후 남은 폭탄 갯수 비교
	            // 이때 board 의 기본값이 -1 이 될 수 없으므로 nBomb 에 1을 더해 nBomb == 0 의 경우 걸러지는걸 막음
				if ((board[d] >> 1) >= tmp.nBomb + 1) continue; 
				if (board[d] & 0b1)                  // 이 위치가 가 `1` 일 때
				{
					if (tmp.nBomb > 0 && day)        // 폭탄이 있고 낮일 때만 간다.
					{
						q.push(E(d, tmp.nBomb - 1));
						board[d] = (tmp.nBomb + 1 << 1) | 0b1;
					}
				}
				else { // 이 위치가 `0` 일 때
					q.push(E(d, tmp.nBomb));
					board[d] = (tmp.nBomb + 1 << 1);
				}
			}
			if (!day) q.push(E(tmp.pos, tmp.nBomb)); // 밤에만 쉬어도 충분하다.
		}
	}
	cout << -1;
}