백준 16235 나무 재테크 파이썬

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

16235번: 나무 재테크

재미있는 구현 문제였다.

하지만 파이썬에서는 시간제안이 좀 빡빡했던거 같다.

원래 봄, 여름, 가을, 겨울을 따로 구현했었고 가을에 나무를 추가할때 sort를 썼다.

시간초과가 나서 봄 + 여름을 합치고 제출했는데 또 43%부분에서 시간초과가 났다, 마지막으로 deque를 사용해 작은것 부터 양분을 먹을 수 있게 sort부분은 appendleft(1)로 고쳐주니 겨우 통과했다.

import sys
from collections import deque
input = sys.stdin.readline
def year(s,maps):
    copys = []
    for i in range(n):#봄
        for j in range(n):
            if maps[i][j]!=[]:
                e = 1#여름부분 합쳐주기 위한 부분. (한번이라도 죽으면 그 이후는 무조건 죽음)
                save = deque()
                for w in maps[i][j]:
                    if s[i][j]-w>=0 and e == 1:
                        s[i][j]-=w
                        save.append(w+1)
                        if (w+1)%5==0:#5의 배수이니 가을에 번식을 할 수 있음
                            copys.append((i,j))#번식하는 나무의 위치를 저장
                    else:
                        s[i][j]+=int(w/2)#죽은 나무이기 때문에 양분을 더해줌.
                        e=0#이 이후 나무도 모두 죽은 나무임을 명시해줌.
                maps[i][j] = save#살아남아 성장한 나무를 maps에 저장함.
   
  
    while copys:#가을
        x,y = copys.pop()
        for u in range(8):#일반 그래프 탐색처럼 해줌
            nx = x+dx[u]
            ny = y+dy[u]
            if 0<=nx<n and 0<=ny<n:#범위안에 있으므로
                maps[nx][ny].appendleft(1)#+=1
    for i in range(n):#겨울에 나왔던 조건대로 행해줌.
        for j in range(n):
            s[i][j]+=winter[i][j]
    

n,m,k=map(int,input().split())
winter= [list(map(int,input().split())) for _ in range(n)]#겨울에 더해줄 양분
s = [[5]*n for _ in range(n)]#초기 양분
dx=[0,0,1,-1,1,-1,1,-1]#그래프 탐색
dy=[1,-1,0,0,1,-1,-1,1]#그래프 탐색
maps = [[deque()for _ in range(n)] for _ in range(n)]#나무를 저장할 배열
for _ in range(m):
    a,b,r = map(int,input().split())
    maps[a-1][b-1].append(r)#초기 나무의 위치와 나이를 저장해줌
for i in range(k):#k년 반복해줌
    year(s,maps)
re=0#결과
for i in range(n):
    for j in range(n):
        if maps[i][j]!=[]:
            re+=len(maps[i][j])#나무의 개수를 더해줌
print(re)#출력