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

1. 문제 설명

2. 해설

문제 설명대로 구현하고 시뮬레이션하는 전형적인 삼성식 문제. 이런 문제는 코딩 기초체력 기르기에 아주 좋다.

아무튼, 이 문제에서 조심할 조건은 미세먼지는 사방으로 동시에 퍼진다는 조건이다. 이 조건 때문에 우리는 단순히 이중 for문을 돌면서 먼지가 있으면 일정량 퍼지게 구현하면 안 되고, 미리 먼지의 위치와 퍼질 양을 구해놓고 먼지가 퍼지도록 구현해야 한다.

이제 위의 조건을 잘 지키면서 먼지가 퍼지고, 공청기가 작동하는 걸 T번 반복해주면 끝.

3. 코드

pypy3으로 제출했다. swea에서도 파이썬은 pypy3으로 컴파일하니 큰 문제 없을 거다.

from sys import stdin
input = stdin.readline


# 먼지가 확산됨
def diffusion(x, y, diff):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    if room[x][y] != 0:
        for s in range(4):
            sx = x + dx[s]
            sy = y + dy[s]
            
            # 범위를 벗어나는 곳과 공기청정기 위치로는 먼지가 확산되지 않음
            if 0 <= sx < R and 0 <= sy < C and room[sx][sy] != -1:
                room[sx][sy] += diff
                room[x][y] -= diff


# 반시계 방향으로 순환함
def clean_up(x):
    sx, sy = x, 1

    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]

    before = 0
    after = 0
    flag = 0
    while True:
        if sx == x and sy == 0:
            flag = 0
            break

        if sy == C - 1:
            flag = 1

        if sx == 0:
            flag = 2

        if sy == 0:
            flag = 3

        after = room[sx][sy]
        room[sx][sy] = before
        sx += dx[flag]
        sy += dy[flag]
        before = after


# 시계 방향으로 순환함
def clean_down(x):
    sx, sy = x, 1
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    before = 0
    after = 0
    flag = 0
    while True:
        if sx == x and sy == 0:
            flag = 0
            break

        if sy == C - 1:
            flag = 1

        if sx == R - 1:
            flag = 2

        if sy == 0:
            flag = 3

        after = room[sx][sy]
        room[sx][sy] = before
        sx += dx[flag]
        sy += dy[flag]
        before = after


R, C, T = map(int, input().split())
cleaner = []  # 공기청정기 위치
room = []
for i in range(R):
    tmp = list(map(int, input().split()))
    if tmp[0] == -1:
        cleaner.append(i)
    room.append(tmp)

for _ in range(T):
    dust = []
    for i in range(R):
        for j in range(C):
            if room[i][j] >= 5: # 먼지는 칸에 있는 먼지량을 5로 나눈 몫만큼 확산
                dust.append([i, j, room[i][j]//5])

    for x, y, diff in dust:
        diffusion(x, y, diff)

    clean_up(cleaner[0])
    clean_down(cleaner[1])

res = 0
for i in range(R):
    if i in cleaner:
        res += sum(room[i][1:])
    else:
        res += sum(room[i])

print(res)