백준 #17144 미세먼지 안녕! (파이썬)

문제 링크

알고리즘 분류가 구현이라는 말은, 그냥 말그대로 빡구현하면 된다는 거다.
시간 복잡도를 줄일 만한 독특한 기법 같은건 없다.

Off-By-One Error를 조심하자.

import sys
import copy

R, C, T = map(int, sys.stdin.readline().rstrip().split())
room = []
for _ in range(R):
    room.append(list(map(int, sys.stdin.readline().rstrip().split())))

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def diffuse():
    # cpy에는 기존 상태 저장, room을 변화시킴.
    cpy = copy.deepcopy(room)
    for y in range(R):
        for x in range(C):
            if cpy[y][x] == 0 or cpy[y][x] == -1:
                continue
            for dx, dy in DIRS:
                if not (0 <= y+dy < R and 0 <= x+dx < C):
                    continue
                if cpy[y+dy][x+dx] == -1:
                    continue
                room[y+dy][x+dx] += cpy[y][x] // 5
                room[y][x] -= cpy[y][x] // 5
                

def circulate_top():
    # 채우는건 순환 방향 역으로 하는게 편함
    for y in range(TOP_CLEANER_IDX-1, 0, -1): # TOP_CLEANER_IDX-1부터 1까지
        room[y][0] = room[y-1][0]
    for x in range(C-1):
        room[0][x] = room[0][x+1]
    for y in range(TOP_CLEANER_IDX):
        room[y][C-1] = room[y+1][C-1]
    for x in range(C-1, 0, -1): # C-1부터 1까지
        if x == 1:
            room[TOP_CLEANER_IDX][x] = 0
            continue
        room[TOP_CLEANER_IDX][x] = room[TOP_CLEANER_IDX][x-1]

def circulate_down():
    for y in range(DOWN_CLEANER_IDX+1, R-1):
        room[y][0] = room[y+1][0]
    for x in range(C-1):
        room[R-1][x] = room[R-1][x+1]
    for y in range(R-1, DOWN_CLEANER_IDX, -1):
        room[y][C-1] = room[y-1][C-1]
    for x in range(C-1, 0, -1):
        if x == 1:
            room[DOWN_CLEANER_IDX][x] = 0
            continue
        room[DOWN_CLEANER_IDX][x] = room[DOWN_CLEANER_IDX][x-1]
                
def circulate():
    circulate_top()
    circulate_down()

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

TOP_CLEANER_IDX = idx
DOWN_CLEANER_IDX = idx+1
    
for _ in range(T):
    diffuse()
    circulate()

rv = 0
for i in range(R):
    for j in range(C):
        if room[i][j] == 0 or room[i][j] == -1:
            continue
        rv += room[i][j]
print(rv)