백준 15806: 영우의 기숙사 청소

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

 

이 문제는 처음 봤을 단순 BFS로 풀 수 있지 않을까? 란 생각을 했었다.

그런것이라면 정답 비율이 16%로 낮을 이유가 없다.

혹시 시간초과라도 나는 것일까?

 

다시 문제를 천천히 보니 이전에 있었던 곳은 없어진다.

만약 BFS를 쓴다면 이전에 있던 곳을 지워야한다.

그런데, 이러면 시간초과가 날 가능성이 있다.

 

그렇다면 어떻게 해야할까?

사실 이 문제의 해결책은 금방 떠올랐다.

곰팡이가 핀 곳에서 번식을 할 때, 다시 같은 위치에 번식을 언제 할까?

2의 시간이 지났을 때이다.

번식을 하는 방향은 그 반대 방향으로도 번식을 하기 때문이다.

그렇다면, BFS의 visit 배열을 2차원에서 3차원으로 바꾸고,

위치와 함께 해당 시간이 음수인지 짝수인지를 확인하면 이전에 있던 곳을 굳이 지울 필요가 없다.

	for (int t = 0; t < T; t++)
	{
		int s = q.size();
		while (s--)
		{
			int y = q.front().first.first;
			int x = q.front().first.second;
			bool p = q.front().second;
			q.pop();
			for (int d = 0; d < 8; d++)
			{
				int ny = y + dy[d];
				int nx = x + dx[d];
				if (inRange(ny, nx) && !v[ny][nx][!p])
				{
					v[ny][nx][!p] = true;
					q.push({ {ny, nx}, !p });
				}
			}
		}
	}

여기 순조로웠는데, 이 문제에 고전한 이유가 2가지가 있다.

첫 째, 곰팡이가 어떠한 곳이라도 번식할 수 없으면 바로 그냥 지워져야하는데, 이것의 구현에 애먹었다.

둘 째, 시간초과를 우려해서 입력마다 하나씩 큐에 넣고 BFS를 돌리는 방식을 택했다가 어려움을 겪었다.

 

첫 번째 같은 경우에는 처음에 어떠한 곳으로 번식할 수 없다면 모든 답은 항상 0으로 체크했다가 된통을 당하기도 했고, 두 번째는 시간초과를 우려해서 사용했는데, 되려 시간초과가 되었다. 입력을 큐에 넣을 때, 해당 위치를 방문한 적이 있다면, 아예 넣지 않는 방식을 택했었는데, BFS를 t만큼 돌려야하는 만큼 해당 위치를 이미 방문을 했어도, 이전 곰팡이가 닿지 않은 곳 까지 갈 가능성이 있어서, 이 방식은 틀렸었다. 결국, 방문체크를 안하면 되는데, 이러면 시간 초과가 된다.

 

결국 첫 번째는 큐에 넣기 전에 모든 방향을 체크한 뒤에, 번식할 수 없으면 큐에 넣는 방식으로 바꿨고

두 번째는 기존의 모든 시작 위치를 큐에 넣는 것으로 다시 수정하였다.

#include <iostream>
#include <queue>

using namespace std;

int N, M, K, T, MY[90001], MX[90001], KY[90001], KX[90001];
bool v[301][301][2];
int dy[8] = { -1, -1, -2, -2, 1, 1, 2, 2 };
int dx[8] = { 2, -2, 1, -1, 2, -2, 1, -1 };
queue<pair<pair<int, int>, bool>> q;
bool clean = false;
bool inRange(int y, int x)
{
	return y > 0 && x > 0 && y <= N && x <= N;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> K >> T;
	for (int i = 0; i < M; i++)
	{
		cin >> MY[i] >> MX[i];
		bool c = false;
		for (int d = 0; d < 8 && !c; d++)
		{
			if (inRange(MY[i] + dy[d], MX[i] + dx[d]))
				c = true;
		}
		if (c)
		{
			v[MY[i]][MX[i]][0] = true;
			q.push({ {MY[i], MX[i]} , 0});
		}
	}
	for (int i = 0; i < K; i++) cin >> KY[i] >> KX[i];
	for (int t = 0; t < T; t++)
	{
		int s = q.size();
		while (s--)
		{
			int y = q.front().first.first;
			int x = q.front().first.second;
			bool p = q.front().second;
			q.pop();
			for (int d = 0; d < 8; d++)
			{
				int ny = y + dy[d];
				int nx = x + dx[d];
				if (inRange(ny, nx) && !v[ny][nx][!p])
				{
					v[ny][nx][!p] = true;
					q.push({ {ny, nx}, !p });
				}
			}
		}
	}
	for (int i = 0; i < K; i++)
	{
		if (v[KY[i]][KX[i]][T % 2])
		{
			clean = true;
			break;
		}
	}
	if (clean) cout << "YES\n";
	else cout << "NO\n";
}

다소 고전을 했지만, 그래도 재미있는 문제였다.