백준 16235 나무 재테크 (파이썬)

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

16235번: 나무 재테크

나무를 배열 하나에 저장하면서 하는 방식은 도저히 시간 초과를 해결할 수가 없었다

 

1. 겨울에 더할 양분 배열 plus_a, 현재 양분 배열 a, 나무 배열 tree 3개를 만들었다

2. 나무가 있는 해당 tree 좌표에 나이 z를 저장한다

3. 봄+여름, 가을, 겨울 순으로 주어진 조건대로 구현한다

4. 봄, 여름에는 tree에 값이 있으면 나이가 어린 순부터 양분을 먹어야 하므로 정렬을 한다

5. 양분을 줄여나가면서 더 이상 먹을 수 없으면 dead_tree에 양분이 될 나무를 더해준다

6. 양분과 tree 정보를 갱신해준다. 모든 반복문을 끝내고 tree가 비어있으면 0을 출력하고 즉시 끝낸다

7. 가을에는 나무를 하나씩 불러와서 8방향으로 증식시킨 후 1을 append 해준다

8. 겨울에는 plus_a를 a에 더해준다

9. k 해가 지나면 나무 개수를 모두 더하여 출력한다

import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, 1, -1, -1]

n, m, k = map(int, input().split())
plus_a = [list(map(int, input().split())) for _ in range(n)]
a = [[5]*n for _ in range(n)]
tree = [[[] for _ in range(n)] for _ in range(n)]

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

for year in range(k):

    for i in range(n):
        for j in range(n):
            if tree[i][j]:
                tree[i][j].sort()
                temp_tree, dead_tree = [], 0
                for age in tree[i][j]:
                    if age <= a[i][j]:
                        a[i][j] -= age
                        age += 1
                        temp_tree.append(age)
                    else:
                        dead_tree += age // 2
                a[i][j] += dead_tree
                tree[i][j] = []
                tree[i][j].extend(temp_tree)

    if not tree:
        print(0)
        sys.exit()

    for i in range(n):
        for j in range(n):
            if tree[i][j]:
                for age in tree[i][j]:
                    if age % 5 == 0:
                        for dir in range(8):
                            ni = i + dx[dir]
                            nj = j + dy[dir]
                            if 0 <= ni < n and 0 <= nj < n:
                                tree[ni][nj].append(1)

    for i in range(n):
        for j in range(n):
            a[i][j] += plus_a[i][j]

ans = 0
for i in range(n):
    for j in range(n):
        ans += len(tree[i][j])
print(ans)