백준 구현 대비 나무재테크

문제:https://www.acmicpc.net/problem/16235

접근

봄 여름 가을 겨울을 각각 함수로 만들어 도식화 하였다. 테스트케이스를 다 통과했음에도 불구하고 계속해서 시간초과가 났었는데 각 반복문마다 if trees[i][j]: 를 넣어주니 시간초과가 발생하지 않음. 연산의 양이 많지 않더라도 조건에 해당하지 않는 케이스는 건너뛰어주는 것이 시간복잡도 감소에 중요한거같다.

from collections import deque
def spring():
  for i in range(N):
    for j in range(N):
      if trees[i][j]:
        trees[i][j].sort()
        templist=[]
        for x in range(len(trees[i][j])):
          if trees[i][j][x]<=graph[i][j]:
            graph[i][j]-=trees[i][j][x]
            trees[i][j][x]+=1
            templist.append(trees[i][j][x])
          else:
            deadtrees.append([i,j,trees[i][j][x]])
        trees[i][j]=templist
      


def suumer():
  for de in deadtrees:
    graph[de[0]][de[1]]+=de[2]//2
  deadtrees.clear()

def fall():
  tempgraph=[[ [] for i in range(N)] for j in range(N)]
  movelist=[[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]
  for i in range(N):
    for j in range(N):
      if trees[i][j]:
        for x in trees[i][j]:
          if x>=5 and x%5==0:
            for mo in movelist:
              ni,nj=i+mo[0],j+mo[1]
              if 0<=ni<N and 0<=nj<N:
                tempgraph[ni][nj].append(1)

  for i in range(N):
    for j in range(N):
      trees[i][j]+=tempgraph[i][j]



def winter():
  for i in range(N):
    for j in range(N):
      graph[i][j]+=addgraph[i][j]
          

N,M,K=map(int ,input().split())
addgraph=[]
graph=[[5 for i in range(N)] for j in range(N)]
trees=[[[] for i in range(N)] for j in range(N)]
deadtrees=[]
for i in range(N):
  addgraph.append(list(map(int ,input().split())))

for i in range(M):
  x,y,z=map(int, input().split())
  trees[x-1][y-1].append(z)

for i in range(K):
  spring()
  suumer()
  fall()
  winter()
answer=0
for t in trees:
  for c in t:
    answer+=len(c)
print(answer)