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

 

문제

---

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

17144번: 미세먼지 안녕!

 

나의 풀이

---

먼지 확산, 먼지 이동

이 두 가지 함수를 짜면 된다. 

확산 함수를 짤 때 유의할 점은 먼지가 이미 있던 곳으로도 확산이 일어난다는 점이다.

먼지 이동 함수를 짤 때 유의할 점은 공기청정기를 기준으로 해서 위 아래 순환 방향이 다르다는 점과 공기 청정기로 들어간 먼지는 소멸한다는 점이다.

이동 함수를 짤 때 range 설정이 조금 까다롭긴 하나 차근차근 따져보면 풀 수 있다.

제출은 python3이 시간초과가 나서 pypy3로 했다.

 

코드

---

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

import sys
input = sys.stdin.readline
import copy

R, C, T = map(int, input().split())
arr = []
for _ in range(R):
    arr.append(list(map(int, input().strip().split())))
circulator = []
for i in range(R):
    for j in range(C):
        if arr[i][j] == -1:
            circulator.append([i,j])

def diff():
    dust_pos = []
    for i in range(R):
        for j in range(C):
            if arr[i][j] >= 1:
                dust_pos.append([i,j,arr[i][j]])
    for r,c,d in dust_pos:
        for dr, dc in ((-1,0),(1,0),(0,-1),(0,1)):
            nr, nc = r + dr, c + dc
            if 0<=nr<R and 0<=nc<C and arr[nr][nc]!=-1:
                arr[nr][nc] += d//5
                arr[r][c] -= d//5

def move():
    temp = copy.deepcopy(arr)
    
    # upper
    y1, x1 = circulator[0]
    arr[y1][1] = 0
    for i in range(2, C):
        arr[y1][i] = temp[y1][i-1]
    for i in range(y1-1, -1, -1):
        arr[i][C-1] = temp[i+1][C-1]
    for i in range(C-2, -1, -1):
        arr[0][i] = temp[0][i+1]
    for i in range(1, y1):
        arr[i][0] = temp[i-1][0]

    # lower
    y2, x2 = circulator[1]
    arr[y2][1] = 0
    for i in range(2, C):
        arr[y2][i] = temp[y2][i-1]
    for i in range(y2+1, R):
        arr[i][C-1] = temp[i-1][C-1]
    for i in range(C-2, -1, -1):
        arr[R-1][i] = temp[R-1][i+1]
    for i in range(R-2, y2, -1):
        arr[i][0] = temp[i+1][0]

for _ in range(T):
    diff()
    move()
ans = 0
for i in range(R):
    ans += sum(arr[i])
print(ans+2)