백준 15806번 - 영우의 기숙사 청소

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

15806번: 영우의 기숙사 청소

큐와 간단한 규칙을 이용한 구현문제였습니다.

 

 

• 문제 해결 방법

곰팡이 증식 0일차, 1일차 (그림1)

 

곰팡이는 1일이 지나면 위와 같이 8개로 증식합니다. 단순한 풀이 방법으로 1일마다 곰팡이 하나하나 8개로 나누어 저장하는 방법을 생각해 봅시다. N이 최대 300이고 t가 최대 10000이므로 최악의 경우 초기 곰팡이가 90000개이고 10000일 후의 결과를 알아야 할때 대충 (90000 * 8 * 10000) 만큼의 수행시간이 필요하므로 시간제한안에 해결할 수 없습니다.

 

 

 

빨간 곰팡이의 1일 후 증식 결과 (그림2)

위의 그림을 잘 살펴보면 반복되는 규칙을 확인해 볼 수 있습니다.

그림2에서 빨간 곰팡이의 1일 후 증식 결과를 보면 그림1의 0일차의 곰팡이 위치에 다시 곰팡이가 증식된 것을 확인할 수 있습니다. 즉, 2일을 주기로 같은 위치에 계속해서 곰팡이가 증식되는 것입니다.

이 규칙을 이용하기 위해 방문처리하는 배열을 늘려주어 증식여부를 확인하면 문제를 해결할 수 있습니다.

주의할 점은 N이 3보다 작거나 같을 경우 곰팡이가 증식하지 못하는 케이스를 생각해 주어야 합니다.

아래의 그림은 N=3, N=2일때 곰팡이가 증식하지 못하는 경우의 예시입니다. 1은 곰팡이를 나타냅니다.

 

곰팡이가 증식하지 못하는 경우

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;
using tpi = tuple<int,int,int>;

int N,M,K,T;
bool vi[2][301][301]; // 2일을 주기로 증식 확인
int dy[8] = {-1,-2,-2,-1,1,2,2,1};
int dx[8] = {-2,-1,1,2,2,1,-1,-2};

void move(int k){
​​​​queue<tpi> q1, q2;
​​​​int a,b;
​​​​for(int i=0; i<M; i++){
​​​​​​​​cin>>a>>b;
​​​​​​​​q1.push({0,a,b});
​​​​}
​​​​
​​​​for(int t=1; t<=k; t++){
​​​​​​​​queue<tpi> &q = t%2 ? q1 : q2;
​​​​​​​​queue<tpi> &nq = t%2 ? q2 : q1;
​​​​​​​​if(q.empty()) break;

​​​​​​​​while(!q.empty()){
​​​​​​​​​​​​int cm, cy, cx;
​​​​​​​​​​​​tie(cm, cy, cx) = q.front();
​​​​​​​​​​​​q.pop();

​​​​​​​​​​​​for(int i=0; i<8; i++){
​​​​​​​​​​​​​​​​int nm = cm^1; // 2일을 주기로 증식 확인
​​​​​​​​​​​​​​​​int ny = cy + dy[i];
​​​​​​​​​​​​​​​​int nx = cx + dx[i];
​​​​​​​​​​​​​​​​if(ny<1 || nx<1 || ny>N || nx>N) continue;
​​​​​​​​​​​​​​​​if(vi[nm][ny][nx]) continue;
​​​​​​​​​​​​​​​​nq.push({nm, ny, nx});
​​​​​​​​​​​​​​​​vi[nm][ny][nx] = true;
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}
}

int main() {
​​​​ios_base::sync_with_stdio(0);
​​​​cin.tie(0);
​​​​cin>>N>>M>>K>>T;

​​​​move(T);
​​​​int a,b;
​​​​for(int i=0; i<K; i++){
​​​​​​​​cin>>a>>b;
​​​​​​​​if(vi[T%2][a][b]) {
​​​​​​​​​​​​cout<<"YES";
​​​​​​​​​​​​return 0;
​​​​​​​​}
​​​​}
​​​​cout<<"NO";
}