https://www.acmicpc.net/problem/17144
"""
"""
from sys import stdin
input = stdin.readline
r, c, t = map(int, input().split()) # r, c : 좌표, t : 시간(초)
pan = [ [0] + list(map(int, input().split())) for _ in range(r) ] # -1 : 공기청정기, 그 이외의 숫자 : 미세먼지 양
pan.insert(0, [0] * (c+1))
dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
def fine_dust(): # 미세먼지를 확산 시키는 함수
dust = []
for i in range(1, r+1):
for j in range(1, c+1):
if pan[i][j] > 0: # 만약 미세먼지가 있다면 좌표와 미세먼지 양을 담는다.
dust.append((i, j, pan[i][j]))
pan[i][j] = 0 # 미세먼지가 있다면 0으로 초기화
for x, y, z in dust: # x, y : 미세먼지 좌표, z : 미세먼지 양
spread_cnt = 0
for k in range(4):
if 1 <= x + dx[k] <= r and 1 <= y + dy[k] <= c: # 범위를 벗어나지 않고 공기청정기 자리가 아니라면
if pan[x+dx[k]][y+dy[k]] != -1:
pan[x+dx[k]][y+dy[k]] += z // 5 # 미세먼지를 확산한다.
spread_cnt += 1 # 미세먼지가 확산된 횟수
pan[x][y] += z - (z//5 * spread_cnt) # 미세먼지 자리는 확산된 횟수를 이용해서 적절한 양을 다시 넣어 준다.
air_dx, air_dy = [0, -1, 0, 1], [1, 0, -1, 0] # 동, 북, 서, 남
def air_cleaner(): # 공기 청정기 함수
air = []
air_cleaner_num = 0 # 공기 청정기 번호 (위쪽 부분이 1, 아래쪽 부분이 2가 될 것이다)
for q in range(1, r+1):
for w in range(1, c+1):
if pan[q][w] == -1: # 공기 청정기 위치의 좌표를 담는다.
air_cleaner_num += 1
air.append((q, w, air_cleaner_num))
for e, a, num in air:
a += 1 # 공기청정기 오른쪽 부터 시작하기 위해 열을 +1 해줌
tmp = [0] # 바람이 불기 때문에 첫번째 좌표는 0으로 될 수 밖에 없음
if num == 1: # 1번 공기청정기의 경우
for s in range(4): # 동 -> 북 -> 서 -> 남
while True: # 다음 좌표가 범위를 벗어나지 않거나 공기청정기가 아닌 경우 앞으로 나아간다.
if not (1 <= e+air_dx[s] <= r and 1 <= a+air_dy[s] <= c):
break
if pan[e+air_dx[s]][a+air_dy[s]] == -1:
pan[e][a] = tmp.pop(0) # 공기 청정기 만나는 경우 tmp에 있는 마지막 값은 pop()하고 끝낸다.
break
# 현재 위치의 미세먼지양을 담고 담겨져 있는 미세먼지 양을 현재 위치에 대입
tmp.append(pan[e][a])
pan[e][a] = tmp.pop(0)
# 좌표 업데이트
e, a = e+air_dx[s], a+air_dy[s]
elif num == 2: # 2번 공기청정기의 경우
for s in range(0, -3-1, -1): # 동 -> 남 -> 서 -> 북
while True: # 다음 좌표가 범위를 벗어나지 않거나 공기청정기가 아닌 경우 앞으로 나아간다.
if not (1 <= e + air_dx[s] <= r and 1 <= a + air_dy[s] <= c):
break
if pan[e + air_dx[s]][a + air_dy[s]] == -1:
pan[e][a] = tmp.pop(0) # 공기 청정기 만나는 경우 tmp에 있는 마지막 값은 pop()하고 끝낸다.
break
# 현재 위치의 미세먼지양을 담고 담겨져 있는 미세먼지 양을 현재 위치에 대입
tmp.append(pan[e][a])
pan[e][a] = tmp.pop(0)
# 좌표 업데이트
e, a = e + air_dx[s], a + air_dy[s]
for _ in range(t):
fine_dust() # 미세먼지 확산
air_cleaner() # 공기 청정기
answer = 0
for i in range(1, r+1):
for j in range(1, c+1):
if pan[i][j] > 0: # 공기 청정기 제외하기 위해 '> 0' 으로 작성
answer += pan[i][j]
print(answer)
문제에 주어진 설명 그대로 작성하면 되긴 한다.
하지만 air_cleaner() 부분에서 만약 공기청정기를 만난다면 tmp에 있는 마지막 값까지 pop(0)을 해주어야 하는 부분을 까먹으면 안된다! 만약 pop(0)을 안하고 끝내면 공기 청정기 도착 직전에 좌표는 바람으로 인해 밀린 미세먼지 양이 있다면 그 부분이 누락된다.