CodeDrive

문제:

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 RxC인 격자판으로 나타냈고, 1x1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r,c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r,c)는 r행 c열을 의미한다.

공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r,c)에 있는 미세먼지의 양은 Ar,c 이다.

1초 동안 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

 - (r,c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.

 - 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.

 - 확산되는 양은 Ar,c / 5 이고 소주점은 버린다.

 - (r,c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)x(확산된 방향의 개수) 이다.

2. 공기청정기가 작동한다.

 - 공기청정기에는 바람이 나온다.

 - 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.

 - 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.

 - 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청저기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력:

첫째 줄에 R, C, T (6<=R,C<=50,1<=T<=1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c(-1<=Ar,c<=1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c 가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력:

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

풀이방법:

크게 두 함수로 구성되어 있다. 미세먼지가 확산되는 것을 나타내는 Spread와, 공기청정기가 작동하는 Clean()으로 구성되어 있었다. 매 초마다 Spread와 Clean이 반복된다.

Spread에서는 확산 될 때, 동시에 모든 곳에서 주변으로 퍼지기 때문에 nextD라는 빈 배열을 만들어서 이 곳에 값을 더하는 방식으로 했다.

Clean에서는 브루트포스 방식으로 진행했다. 공기청정기는 두 개의 인덱스를 차지하게 된다. 윗 부분에서는 반시계방향으로 회전하기 때문에 r의 인덱스가 0일 때, 윗 공기청정기 인덱스일 때, c의 인덱스가 0일 때, c-1일 때 공기청정기의 영향을 받는다.

아랫 부분에서는 시계방향으로 회전하면 r의 인덱스가 아랫 공기청정기 인덱스일때, r-1일때, 그리고 c의 인덱스가 0일 때, c-1일 때 영향을 받는다.

함수를 구성하고 나서 채점을 돌렸는데 Python에서는 시간초과가 발생하고, Pypy에서는 통과했다. 너무 비효율적으로 코드를 짠 것 같다.

문제링크:

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