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

 

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

 

 

 

통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검사에서 나쁜 점수를 받으면 벌점을 받게 되고, 벌점이 많이 쌓이면 기숙사에서 퇴사 해야 한다. 영우는 어떤 경우에 벌점을 받는지 궁금하여 기숙사에서 진행하는 청소 검사 시스템에 대해 자세히 조사해 보았다. 기숙사 청소 검사 시스템은 오늘로부터 정확히 t 일이 지나고 검사를 하며, 검사 시간 단축을 위해 방의 특정 부분만 검사한다. 하지만 검사하는 특정 부분 중 한 곳이라도 더럽다면 영우는 벌점을 받게 된다. 영우가 사는 방은 N * N 정사각형 방이며, 기숙사 방바닥에는 곰팡이가 서식하고 있다. 곰팡이는 1 일이 지날 때마다 특이한 방식으로 증식하는데, 그림 1(a)의 곰팡이는 1 일이 지나면 그림 1(b)와 같이 8 군데로 증식되고, 원래의 곰팡이는 사라진다. 만약 곰팡이가 증식해야 하는 부분이 벽으로 막혀 있다면, 그곳으로는 증식하지 못한다. 그림 2 는 두 군데의 곰팡이가 1 일이 지난 후 모습이다.

 

위 그림은 증식방식이다.

 

 

 

해당문제는 처음 보았을때 단순 시물레이션 문제와 같다고 생각할수 있지만

 

그냥 구현하게 된다면  반복적인 처리로인해 계산해야 하는 곰팡이가 기하급수적으로 늘어난다

 

해당 문제를 잘 생각해본다면 최적화 할수있는 부분이 쉽게 보인다.

 

 

 

중앙에서 시작할경우 퍼지는 모습은 아래와 같다

 

 

위 이미지로 알수있는것은  이동 했던 칸에서 다시 원래자리에 곰팡이를 복구 시킨다는 사실이다.

 

그렇다면 해당 위치에 곰팡이가 생기고 하나라도 이동했을경우엔 무한정 곰팡이가 번식한다는 이야기다...으...

 

 

그렇다면 두번째로 생각할수있는것은 

 

해당 위치에서 1턴 쉬면서 반복한다 라는것은 

 

홀수날과 짝수날을 구분지어 두개의 영우의방을 돌아가면 계산한다면,

해당 위치가 이미 곰팡이가 있었던 적이 있었는지도 간단하게 체크할수있다.

 

 

BFS를 사용해서 반복체크를 할때 다음 날의 위치가 일전에 도달한적 있는 위치라면

 

이미 반복했던 위치기에 다시 곰팡이를 그릴 이유가 없다.

 

 

 

 

 

 

하지만 해당 문제는 쉽게 지나칠수 있는 문제가 존재한다.

바로 마지막줄인 "만약 곰팡이가 증식해야 하는 부분이 벽으로 막혀 있다면, 그곳으로는 증식하지 못한다."

 

해당 문제에서 증식 하지못한다면 자연적으로 사라진다.

 

곰곰히 생각해보면 3*3의 가운데 지점 에서만 문제가 될수있다.

 

그 미만(2*2 ,1*1)에서는 곰팡이는 생존이 불가능하고

 

초과되었을때는 어느 장소에 생겨도 한무반복은 예정되어있다.

 

 

 

예외 예제를 보자 

해당위치는 3*3이상에서 의 유일한 사라지는 위치다. 이부분만 조심해서 문제를 풀자.

 

 

 

프로그램의 입력은 표준 입력으로 받는다. 첫 줄에 영우의 방의 크기, 방에 있는 곰팡이의 개수, 청소 검사 시스템이 검사하는 방바닥 좌표의 개수, 청소 검사가 실시 되기까지 남은 일수인 N M K t 가 주어진다.

(1 ≤ N ≤ 300, 0 ≤ M ≤ N2, 0 ≤ K ≤ N2, 1 ≤ t ≤ 10000)

 

둘째 줄부터 M 개의 줄에 걸쳐 영우의 방에 있는 곰팡이의 위치인 Mx My가 주어진다.(1 ≤ Mx, My ≤ N)

다음 줄부터 K 개의 줄에 걸쳐 검사관이 검사하는 방바닥의 위치인 Kx Ky가 주어진다.(1 ≤ Kx, Ky ≤ N)

 

 

N 영우의 방크기

M 방에있는 곰팡이의 개수

K 검사하는 방바닥 좌표의개수

t  청소 검사가 실시 되기까지 남은 일수

 

 

5 2 4 1

 

2 1

3 3

 

3 1

3 2

3 3

3 4

 

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void ClearRoom() {

	int N, M, K, t;
	cin >> N >> M >> K >> t;
	std::vector<vector<bool>> vmap(N + 1, vector<bool>(N + 1, false)),
		avmap(N + 1, vector<bool>(N + 1, false)),
		* Nextpm, * Dpm;
	std::queue <int> QSearchX;
	std::queue <int> QSearchY;


	int x = 0, y = 0;
	for (int i = 0; i < M; i++)
	{
		cin >> x >> y;
		vmap[--x][--y] = true;
		QSearchX.push(x);
		QSearchY.push(y);
	}

	const int dy[8] = { -1,-2,-2,-1,1,2,2,1 };
	const int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
	for (int i = 0; i < t; ++i) {

		int Qsize = QSearchX.size();
        
        //오늘 방과 내일 영우의 방
		Dpm = &(((i % 2) != 0) ? avmap : vmap);
		Nextpm = &(((i % 2) == 0) ? avmap : vmap);
		//현재 일수에 움직이는 곰팡이
        for (int j = 0; j < Qsize; j++)
		{
			int datax = QSearchX.front();
			int datay = QSearchY.front();
			QSearchX.pop();
			QSearchY.pop();
			bool check = false;
            
            //8방향 곰팡이 번식
			for (int i = 0; i < 8; ++i) {
				x = datax + dx[i];
				y = datay + dy[i];
				
                //곰팡이 가 번식 가능한지 확인후 번식
                if ((x < N && x >= 0 && y < N && y >= 0) && !(*Nextpm)[x][y])
				{
                	(*Nextpm)[x][y] = true;
                    // 다음 번식 예정인 queue
					QSearchX.push(x);
					QSearchY.push(y);
					check = true;
				}
			}
            //만약 해당 곰팡이가 어느 하나도 이동하지 못햇더라면
            //이 곰팡이는 다음날 죽는다.
			if (!check) {
				(*Dpm)[datax][datay] = false;
			}
		}
	}
	bool IsClear = false;
	Dpm = &(((t % 2) != 0) ? avmap : vmap);
    
    //검수의 날
	for (int i = 0; i < K; i++)
	{
		cin >> x >> y;
		if ((*Dpm)[x-1][y-1])IsClear = true;
		if (IsClear)break;
	}
	cout << (IsClear ? "YES" : "NO");
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	ClearRoom();
}

 

 

 

해당 문제를 풀며 

배열 문제의 1입력 과 0입력을 확실하게 잡아야했고

 또한 문제 t의 정의에 대해 확실하게 잡아야했다.

 

 

 

 

아래 시뮬레이터로 문제의 경우의 수를 확인해보자

 

Knight Movement Simulator

Size:

Step: 0 Active positions: 0

 

 

영우가 빠른시일 내로 청소하지 않는다면 집은 곰팡이에게 잠식당해 버릴지도 모른다.