[BOJ] 17144. 미세먼지 안녕!(python)

📌문제

💪아이디어

1. 공기청정기 위치
   

2. 미세먼지 위치
   미세먼지는 동시에확산되기 때문에 확산 전에 미세먼지의 위치를 queue에 미리 넣는다.
   

3. 미세먼지 확산
   미리 넣어놓은 미세먼지 위치를 돌면서 미세먼지 양을 감소시킨다.
   이때 주의할 점은 확산되는 양을 계산할 때 board의 값을 직접 접근해서는 안된다. 앞에서 확산된 후 더해져 갱신된 값으로 확산될 수도 있기 때문이다.

미세먼지의 위치를 queue에 넣을 때 미세먼지 양도 함께 넣어주면 별도의 배열복사를 하지 않아도 된다.

1. 공기청정기 순환
   위쪽 공기청정기는 반시계방향, 아래쪽 공기청정기는 시계방향으로 board값을 옮겨준다.
   

2. t초 동안 2번 ~ 4번 반복하기
   
3. 남은 미세먼지 양구하기
   board값을 모두 구하면 공기청정기값인 -1가 두번 더해지기때문에 결과값에 +2해준다.
   

🥂코드

import sys; input = sys.stdin.readline
from collections import deque

dy = (-1,0,1,0)
dx = (0,1,0,-1)

def initQ():
    for i in range(1,r+1):
        for j in range(1,c+1):
            if board[i][j] > 0: queue.append((i,j,board[i][j]))

def spread():
    while queue:
        y,x, amount = queue.popleft()
        vol = amount // 5
        if vol == 0: continue
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 < ny <= r and 0 < nx <= c and board[ny][nx] != -1:
                board[ny][nx] += vol
                board[y][x] -= vol

def cleaning(aircleaner,move):
    y, x = aircleaner
    tmp = 0
    i = 1
    ny, nx = y, x
    for _ in range(4):
        ny, nx = ny + dy[i], nx + dx[i]
        while True:
            tmp, board[ny][nx] = board[ny][nx], tmp
            if 1 <= ny + dy[i] <= r and 1 <= nx + dx[i] <= c:
                ny += dy[i]
                nx += dx[i]
            else: break
            if ny == y and nx == x: break
        i = (i + move) % 4

r, c, t = map(int,input().split())
board = [[0 for _ in range(c+1)] for _ in range(r+1)]
airCleaner = []
queue = deque()

for i in range(1,r+1):
    board[i][1:] = list(map(int,input().split()))
    if len(airCleaner) != 2:
        for j in range(1,c+1):
            if board[i][j] == -1: airCleaner.append((i,j))

for _ in range(t):
    initQ()
    spread()
    cleaning(airCleaner[0],-1)
    cleaning(airCleaner[1],1)

answer = 0
for b in board:
    answer += sum(b)
print(answer + 2)