백준 17144 : 미세먼지 안녕! (Python)

liliili·2023년 3월 6일

백준

목록 보기

196/214

import sys
input=sys.stdin.readline
LMI=lambda:list(map(int,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
G=lambda x:[ LMI() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

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

"""
미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다
미세먼지가 있는 곳으로도 확산이 된다. 
이때 조건 - (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다. - 먼저 실행되고
조건 - (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다. - 이 실행된다.
"""
def Diffusion():
    P=[] ; L=[]
    for i in range(N):
        for j in range(M):
            if graph[i][j]>0:
                count=0
                for k in range(4):
                    nx,ny=i+dx[k],j+dy[k]
                    if 0<=nx<N and 0<=ny<M and graph[nx][ny]!=-1:
                        P.append([nx,ny,graph[i][j]//5])
                        count+=1
                L.append([i,j,graph[i][j]-(graph[i][j]//5)*count])
    for x,y,value in L:
        graph[x][y]=value
    for x,y,value in P:
        graph[x][y]+=value

def Clean():

    x,y=cleaner[0][0],cleaner[0][1]
    L=[]

    while y+1<M:
        y+=1
        L.append([x,y+1,graph[x][y]])
    L[-1][0]-=1 ; L[-1][1]-=1
    while x>0:
        x-=1
        L.append([x-1,y,graph[x][y]])
    L[-1][0]+=1 ; L[-1][1]-=1
    while y>0:
        y-=1
        L.append([x,y-1,graph[x][y]])
    L[-1][0]+=1 ; L[-1][1]+=1
    while graph[x+1][y]!=-1:
        x+=1
        L.append([x+1,y,graph[x][y]])

    L.pop()
    for x,y,value in L:
        graph[x][y]=value

    x,y=cleaner[1][0],cleaner[1][1]
    L.clear()

    while y + 1 < M:
        y += 1
        L.append([x, y + 1, graph[x][y]])
    L[-1][0]+=1 ; L[-1][1]-=1
    while x+1< N:
        x+=1
        L.append([x+1,y,graph[x][y]])
    L[-1][0]-=1 ; L[-1][1]-=1
    while y>0:
        y-=1
        L.append([x,y-1,graph[x][y]])
    L[-1][0]-=1 ; L[-1][1]+=1
    while graph[x-1][y]!=-1:
        x-=1
        L.append([x-1,y,graph[x][y]])

    L.pop()
    for x, y, value in L:
        graph[x][y] = value
    if cleaner[0][1]+1<M:
        graph[cleaner[0][0]][cleaner[0][1]+1]=graph[cleaner[1][0]][cleaner[1][1]+1]=0

def All():
    total = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j]>0:
                total+=graph[i][j]
    return total

N,M,T=MI()
graph=G(N)
cleaner=[]
for i in range(N):
    for j in range(M):
        if graph[i][j]==-1:
            cleaner.append((i,j))

for i in range(T):
    Diffusion()
    Clean()
print(All())