문제

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

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

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

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

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

• (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
• 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
• 확산되는 양은 Ar,c/5이고 소수점은 버린다.
• (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.

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초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

아이디어

✅ dust라는 리스트를 새로 만들어서 확산된 먼지들을 표시한 후, 회전시키는 것을 반복한다.

✔️ 코드 설명
1. L초 동안 반복한다.
2. -1이면 공기청정기의 위치 이므로 air라는 리스트에 추가한다.(무조건 1열에 있으므로 y값은 저장하지 않아도 된다.)
3. 5이상인 경우에 대해서 상하좌우를 조사해 dust에 값을 저장한다.

4. 공기 청정기 방향에 맞춰 회전한다.
   4.1 반시계 방향으로 회전하는 경우
   맨 윗줄과 첫번째 공기 청정기가 있는 공간은 한 칸씩 밀리는 것과 같으므로 하나씩 미루고 끝 부분 원소를 저장해두고 삭제한다.
   4.2 시계 방향으로 회전하는 경우
   위와 마찬가지로 두 번째 공기 청정기가 있는 공간과 맨 마지막 줄을 한 칸씩 미루고, 끝 부분 원소 저장하고 삭제한다.

5. 끝 부분 for문을 이용해서 하나씩 미룬다.

6. arr를 dust로 업데이트 해야한다. (❗이 과정이 없으면 처음 배열 상태로 계속 반복된다.)

7. 마지막에 모든 원소값을 더한 후 공기 청정기에서 -2가 됐기 때문에 +2를 해준다.

내 코드_pypy3

:: python으로 하면 시간초과, pypy3로 해야 한다.

import copy

r, c, l = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(r)]

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]  #상하좌우 검사
air = []

for x in range(l):  #l번 반복(l초 후)
    dust = [[0] * c for x in range(r)]
    for i in range(r):
        for j in range(c):
            cnt = 0 #상,하,좌,우 몇 개로 확산됐는지 표시
            if arr[i][j] == -1:
                air.append(i)
                continue
            elif arr[i][j] >= 5:    #5보다 작은 경우는 5로 나눈 몫이 0이므로 할 필요 없다.
                for k in range(4):
                    nx = i + direction[k][0]
                    ny = j + direction[k][1]
                    if 0 <= nx < r and 0 <= ny < c and arr[nx][ny] != -1:   #공기 청정기의 위치는 빼야한다.
                        dust[nx][ny] += arr[i][j]//5
                        cnt += 1
            dust[i][j] += arr[i][j] - (arr[i][j]//5)*cnt

    #회전 반시계
    dust[0].append(0)
    l = dust[0][0]
    del dust[0][0]

    dust[air[0]].insert(0,0)
    rr = dust[air[0]][-1]
    del dust[air[0]][-1]

    lx = air[0]
    rx = 0
    for i in range(air[0]):
        if i == air[0] - 1:
            dust[lx][0] = l
            dust[rx][c-1] = rr
            dust[air[0]][0] = -1    #공기 청정기 위치는 -1로 지정
        else:
            dust[lx][0] = dust[lx-1][0]
            dust[rx][c-1] = dust[rx+1][c-1]
            lx -= 1
            rx += 1

    #회전 시계
    dust[air[1]].insert(0, 0)
    rr = dust[air[1]][-1]
    del dust[air[1]][-1]

    dust[-1].append(0)
    l = dust[-1][0]
    del dust[-1][0]

    lx = air[1]
    rx = r-1
    for i in range(r-air[1]-1):
        if i == r-air[1]-2:
            dust[lx][0] = l
            dust[rx][c-1] = rr
            dust[air[1]][0] = -1    #공기 청정기 위치는 -1로 지정
        else:
            dust[lx][0] = dust[lx+1][0]
            dust[rx][c-1] = dust[rx-1][c-1]
            lx += 1
            rx -= 1
    arr = copy.deepcopy(dust)

print(sum(sum(dust, []))+2)