본문 바로가기

카테고리 없음

[백준 17144번] 미세먼지 안녕! (Python3)

import sys
input = sys.stdin.readline
from collections import deque
import copy

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

N,M,T = map(int,input().split())

room = []
for i in range(N):
  room.append(list(map(int,input().split())))

def spread():
  dq = deque()
  for i in range(N):
    for j in range(M):
      if room[i][j]==-1 or room[i][j]==0:
        continue
      s = room[i][j]//5
      count = 0
      for k in range(4):
        y = i+dy[k]
        x = j+dx[k]
        if y>=0 and y<N and x>=0 and x<M:
          if room[y][x] == -1:
            continue
          count += 1
          dq.append((s,y,x))
      room[i][j] -= s*count
  while dq:
    s,y,x = dq.pop()
    room[y][x] += s

def airclean(x):
  dq = deque()
  dq.append((x,1,0))
  dq.append((x+1,1,0))
  for i in range(1,M):    #첫째 가로줄
    dq.append((0,i-1,room[0][i]))
  for i in range(1,M-1):    #공기청정기 윗부분 가로줄
    dq.append((x,i+1,room[x][i]))
  for i in range(x):    #세로줄
    dq.append((i+1,0,room[i][0]))
  for i in range(1,x+1):    #맨끝 세로줄
    dq.append((i-1,M-1,room[i][M-1]))
    
  for i in range(1,M):
    dq.append((N-1,i-1,room[N-1][i]))
  for i in range(1,M-1):
    dq.append((x+1,i+1,room[x+1][i]))
  for i in range(x+1,N):
    dq.append((i-1,0,room[i][0]))
  for i in range(x+1,N-1):
    dq.append((i+1,M-1,room[i][M-1]))
  while dq:
    y1,x1,s = dq.pop()
    room[y1][x1] = s
  room[x][0] = room[x+1][0] = -1

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

for i in range(T):
  spread()
  airclean(cleaner)

result = 0
for i in room:
  result += sum(i)

print(result+2)

코드가 좀 지저분해서 이게 맞나 싶었는데 맞더라

airclean 함수를 재귀함수로 좀 간단하게 할 수 없을까 고민해봤는데, 짜려면 짤 순 있는데 그거나 for문 때려박는거나 별다를게 없을거같아서 그만뒀다.

 

deepcopy를 안쓰려고 deque로 일단 값을 다 저장한 후에 나중에 불러오는 방법을 사용했는데 (먼지가 한번에 확산해야 하므로) 다른 사람들 풀이 보니까 그냥 0으로된 리스트 이용하는 방법이 더 나은거 같기도 하다.

 

 

오늘의 교훈) 굳이 제한이 빡빡하지 않다면 대충 지저분한 함수로 풀자