[백준] 나무재테크

문제

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

알고리즘

본 문제는 시뮬레이션 문제로 나와있는 과정을 따라가면 그리 어렵지 않은 문제이다.
하지만 중요한 구현상에 있어서 나무를 배열 하나에 저장할 시 시간 초과 문제를 해결할 수 없다.

따라서 다음과 같이 배열을 세개 만들어야 한다.

real_board : 매해 겨울에 추가되는 양분의 수를 담아둔배열 ,

board : 실제 땅에 있는 양분을 담아둔 배열

tree_board : 해당하는 땅에 들어있는 나무의 나이를 담아둔 배열

구현 방식은 다음과 같다.

1. tree_board 에 나무의 나이를 list 로써 저장한다.
2. 봄 -> 여름 -> 가을 -> 겨울 순으로 코드를 구현함.
3. 이때, 문제의 조건에 나이가 어린순으로 양분을 먹음으로 정렬을 해주어야 한다.
4. 양분이 없어 죽은 나무는 dead_tree 에 값을 추가한다.
5. 봄 여름이 지나감에 따라 땅의 양분, 나무의 나이를 갱신해준다.
6. 가을은 각 나무의 나이가 5의 배수일 시 8방향으로 나이를 1 더해준다.
7. 이때, 범위를 벗어나는 위치의 땅의 경우 갱신이 불가하므로 dy , dx list를 활용하여 값을 갱신한다.
8. 겨울에는 매해 board 변수에 real_board 값을 더해준다.
9. k 년동안 반복한 뒤 tree_count 변수 출력한다.

import sys

input = sys.stdin.readline

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

N, M, K = map(int, input().split())
real_board = [list(map(int, input().split())) for _ in range(N)]
board = [ [5] * N for _ in range(N)]
tree_board = [ [ [] for _ in range(N) ] for _ in range(N)]

tree_count = 0

for _ in range(M):
    x, y, z = map(int,input().split())
    tree_board[x-1][y-1].append(z)
    tree_count += 1
    
for year in range(K):
    #spring
    for i in range(N):
        for j in range(N):
            if tree_board[i][j]:
                tree_board[i][j].sort()
                temp_tree, dead_tree = [], 0
                for age in tree_board[i][j]:
                    if age <= board[i][j]:
                        board[i][j] -= age
                        age += 1
                        temp_tree.append(age)
                    else :
                        tree_count -= 1
                        dead_tree += age // 2
                board[i][j] += dead_tree
                tree_board[i][j] = []
                tree_board[i][j].extend(temp_tree)
    #summer but did in spring
    
    #fall
    for i in range(N):
        for j in range(N):
            if tree_board[i][j]:
                for age in tree_board[i][j]:
                    if age % 5 == 0:
                        for k in range(8):
                            nx = i + dy[k]
                            ny = j + dx[k]
                            if 0<= nx < N and 0 <= ny < N:
                                tree_count += 1
                                tree_board[nx][ny].append(1)
    
    #winter
    for i in range(N):
        for j in range(N):
            board[i][j] += real_board[i][j]
            
print(tree_count)