[백준 17144] 미세먼지 안녕! (python)

17144번: 미세먼지 안녕!

---

import sys
from copy import deepcopy
from collections import deque
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
input = sys.stdin.readline
R, C, T = map(int, input().split())
arr = []
diff = []
for _ in range(R):
    arr.append(deque(map(int, input().split())))

def diffusion(x, y):
    current = arr[x][y]
    divide = arr[x][y]//5
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0 <= nx < R and 0 <= ny < C and arr[nx][ny] != -1:
            diff[nx][ny] += divide
            current -= divide
    diff[x][y] += current


def airclean(x):
    arr[x][0] = 0
    arr[x+1][0] = 0
    for i in range(0, x):
        arr[i].append(arr[i+1].pop())
    for i in range(x, 0, -1):
        arr[i].appendleft(arr[i-1].popleft())
    for i in range(R-1, x+1, -1):
        arr[i].append(arr[i-1].pop())
    for i in range(x+1, R-1):
        arr[i].appendleft(arr[i+1].popleft())
    arr[x][0] = -1
    arr[x+1][0] = -1


airclean_p = 0
for i in range(R):
    if arr[i][0] == -1:
        airclean_p = i
        break

for _ in range(T):
    diff = [deque([0]*C) for _ in range(R)]
    diff[airclean_p][0] = -1
    diff[airclean_p+1][0] = -1
    for i in range(R):
        for j in range(C):
            if arr[i][j] > 0:
                diffusion(i, j)
    arr = deepcopy(diff)
    airclean(airclean_p)

answer = 0
for i in range(R):
    for j in range(C):
        if arr[i][j] > 0:
            answer += arr[i][j]
print(answer)

먼지가 동시에 확산한다는 점이 중요하다. 시간 초과나서 pypy3으로 제출함

1. 먼지 증감 배열을 만들어서 증감체크 (원래 배열을 기준으로 잡아야하기 때문에 diff배열 생성)
2. 공기청정 deque를 사용하여 먼지 옮겨줌