[백준] 16235번 : 나무 재테크

16235번: 나무 재테크

해당문제는 구현 문제로, 봄,여름,가을,겨울을 각각 나누어서 기능들을 구현 하면 문제를 쉽게 해결 할 수 있습니다.

1. 봄
   1. 나무가 자신의 나이만큼 양분을 먹는다
   2. 1x1 크기의 칸에 있는 양분만 먹을 수 있다.
   3. 하나의 칸에 여러 개 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
   4. 자신의 나이만큼 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.

<aside> 💡 봄에서의 가장 큰 포인트는 나이가 어린 나무부터 양분을 먹으므로 우선순위 큐를 사용해야합니다.

</aside>

1. 여름
   1. 죽은 나무가 양분으로 변하게된다, 죽은 나무는 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다.
2. 가을
   1. 나무가 번식하고, 나무는 나이가 5의 배수이어야하며 인접한 8개의 칸에 나무가 1인 나무가 생긴다.
   2. 상도의 땅을 벗어난 칸에는 나무가 생기지 않는다.

<aside> 💡 여기서 인접한 나무가 1인 나무가 생길때 기존에 있던 우선순위큐에 첫번째 인덱스에 나무를 넣어야한다. ( 나무는 어린 나무부터 양분을 먹어야 하기 때문 )

</aside>

1. 겨울
   1. 땅에 양분을 추가한다.

우선순위 큐는 파이썬 내장 Deque를 사용하였습니다.

중요 !! : (봄,여름), (가을,겨울)은 각각의 기능에 대하여 독립적이기 때문에 시간복잡도를 줄이기 위하여 같이 묶어준다.

import sys
from collections import deque
from copy import deepcopy
from pprint import pprint

input = sys.stdin.readline

N, M, K = map(int, input().rstrip().split())
land = [[5 for _ in range(N+1)] for _ in range(N+1)]
ar = [[0 for _ in range(N+1)] for _ in range(N+1)]
tree = [[deque() for _ in range(N+1)] for _ in range(N+1)]
move = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]

for i in range(1, N+1):
    ar[i] = [0] + list(map(int, input().split()))

for _ in range(M):
    y, x, z = map(int, input().split())
    tree[y][x].append(z)

def spring_sumer(land, tree):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            newtree = deque()
            died = 0
            while tree[i][j]:
                size = tree[i][j].popleft()
                if land[i][j] >= size:
                    land[i][j] -= size
                    newtree.append(size+1)
                else:
                    died += size//2

            tree[i][j] = newtree
            land[i][j] += died
def fall_winter(tree, ar):
    temp_tree = []
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            land[i][j] += ar[i][j]
            for size in tree[i][j]:
                if (size % 5) == 0: # 5의 배수이면 나머지 값이 0이다.
                    for dy, dx in move:
                        ny = dy + i
                        nx = dx + j
                        if N >= ny >= 1 and N >= nx >= 1:
                            temp_tree.append((ny, nx))

    for y, x in temp_tree:
        tree[y][x].appendleft(1)

def getalivetree(tree):
    cnt = 0
    for i in range(1, N+1):
        for j in range(1, N+1):
            cnt += len(tree[i][j])

    return cnt

while K > 0:
    spring_sumer(land, tree)
    fall_winter(tree, ar)
    K -= 1

print(getalivetree(tree))