[백준 16235] 나무 재테크 (python)

16235번: 나무 재테크

---

나무를 3차원으로 저장하자! 시간초과가 나서 PyPy3으로 제출하였다.

처음 시도: 정렬을 할 필요가 없게 deque를 쓰는 것까진 시도했으나 시간초과가 났다. 더이상 고칠데가 없어서 다른 사람 코드를 참고하였다.

 

시도했지만 시간 초과가 난 코드

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

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

N, M, K = map(int, input().split())
arr = [[5]*N for _ in range(N)]
s2d2 = []
tree = deque()
remain = deque()
dead = deque()
for _ in range(N):
    s2d2.append(list(map(int, input().split())))

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

while K > 0:
    while tree:
        x, y, z = tree.popleft()
        if arr[x][y] < z:
            dead.append([x, y, z//2])
        else:
            arr[x][y] -= z
            remain.append([x, y, z+1])

    while dead:
        x, y, z = dead.popleft()
        arr[x][y] += z

    while remain:
        x, y, z = remain.popleft()
        tree.append([x, y, z])
        if z % 5 == 0:
            for j in range(8):
                nx = x + dx[j]
                ny = y + dy[j]
                if 0 <= nx < N and 0 <= ny < N:
                    tree.appendleft([nx, ny, 1])

    for i in range(N):
        for j in range(N):
            arr[i][j] += s2d2[i][j]

    K -= 1

print(len(tree))

 

처음에 나무를 입력받을 때 한 위치에는 한 나무만 있기 때문에 정렬할 필요가 없었다.

나무를 3차원(tree)으로 저장하니깐 처리해줄때 정렬되있으므로 한꺼번에 처리할 수 있었다. 

 

• 봄: 나이보다 양분이 많다면 나이(tree[i][j][k])를 1 올려준다.
• 여름: 나이보다 양분이 적다면 그 뒤에 있는 나무도 다 적기 때문에 죽은 나무로 취급해 양분을 더해준다.
• 가을: 8방향으로 나무 번식을 해준다. 새로 나는 나무는 앞으로 넣어준다. (그러면 정렬을 할 필요가 없다.)
• 겨울: s2d2를 더해준다.

 

최종코드

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

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

N, M, K = map(int, input().split())
arr = [[5]*N for _ in range(N)]
s2d2 = []
tree = [[deque() for _ in range(N)] for _ in range(N)]
for _ in range(N):
    s2d2.append(list(map(int, input().split())))
for _ in range(M):
    x, y, z = map(int, input().split())
    tree[x-1][y-1].append(z)

while K > 0:
    # 봄
    for i in range(N):
        for j in range(N):
            t_len = len(tree[i][j])
            for k in range(t_len):
                if arr[i][j] >= tree[i][j][k]:
                    arr[i][j] -= tree[i][j][k]
                    tree[i][j][k] += 1
                else:
                    # 여름
                    for _ in range(k, t_len):
                        arr[i][j] += tree[i][j].pop() // 2
                    break

    # 가을
    for i in range(N):
        for j in range(N):
            for z in tree[i][j]:
                if z % 5 == 0:
                    for l in range(8):
                        nx = i + dx[l]
                        ny = j + dy[l]
                        if 0 <= nx < N and 0 <= ny < N:
                            tree[nx][ny].appendleft(1)
            #겨울
            arr[i][j] += s2d2[i][j]
    K -= 1

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