Algorithm/BOJ
영우의 기숙사 청소 - 15806
jhg0406
2020. 3. 15. 04:19
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
//15806 - 영우의 기숙사 청소
#include <iostream>
#include <queue>
using namespace std;
int N, M, K, T;
bool arr[2][301][301];
int xarr[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int yarr[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
queue<int> xQ[2];
queue<int> yQ[2];
void init()
{
cin >> N >> M >> K >> T;
int x, y;
for(int i = 0; i<M; ++i)
{
cin >> x >> y;
arr[0][x][y] = true;
xQ[0].push(x);
yQ[0].push(y);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
init();
int x, y;
for(int i = 0; i<T; ++i)
{
while(!xQ[i%2].empty())
{
x = xQ[i%2].front(), xQ[i%2].pop();
y = yQ[i%2].front(), yQ[i%2].pop();
for(int j = 0; j<8; ++j)
if(x+xarr[j] >= 1 && x+xarr[j] <= N && y+yarr[j] >= 1 && y+yarr[j] <=N)
if(!arr[(i+1)%2][x+xarr[j]][y+yarr[j]])
{
arr[(i+1)%2][x+xarr[j]][y+yarr[j]] = true;
xQ[(i+1)%2].push(x+xarr[j]);
yQ[(i+1)%2].push(y+yarr[j]);
}
}
}
bool flag = false;
for(int i = 0; i<K; ++i)
{
cin >> x >> y;
if(arr[T%2][x][y])
flag = true;
}
if(flag)
cout << "YES";
else cout << "NO";
}
|
cs |
https://www.acmicpc.net/problem/15806
15806번: 영우의 기숙사 청소
통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검사에서 나쁜 점수를 받으면 벌점을 받게 되고, 벌점이 많이 쌓이면 기숙사에서 퇴사 해야 한다. 영우는 어떤 경우에 벌점을 받는지 궁금하여 기숙사에서 진행하는 청소 검사 시스템에 대해 자세히 조사해 보았다. 기숙사 청소 검사 시스템은 오늘로부터 정확히 t 일이 지나고 검사를
www.acmicpc.net
영우의 기숙사 청소
매일 곰팡이가 퍼지는것을 배열에 저장해 마지막 날에 검사하는 위치에 곰팡이가 있는지 없는지 확인하면 됩니다.
이때, 곰팡이가 퍼지는 패턴을 보면 이틀 전의 곰팡이가 그대로 오늘 똑같은 위치에 있게 된다는 것을 알수 있습니다.
무슨말이냐면, 0일날 있던 곰팡이는 2일날 그대로 있고, 2일날 있는 곰팡이는 4일날 그대로 있게 됩니다!
위의 패턴을 이용해 곰팡이가 사라지는것을 지우는게 아니라 배열을 두개 유지해 곰팡이를 지우지 않고, 곰팡이가 없는곳에만 추가해준다면 주어진 시간안에 문제를 해결할수 있습니다!
(규칙 찾는것이 어려웠습니다. 곰팡이가 퍼지는 모양이 체스 나이트 움직임과 같은데, 이틀 주기로 원래 있던모양은 유지되고 새로운 모양이 원래 모양에 추가된다는 것을 기억하면 좋을거 같습니다!)
