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

16235번: 나무 재테크

16235번: 나무 재테크

📄 문제개요

• 봄 : 나무의 나이가 가장 작은 순서부터, 자신의 나이만큼 양분을 먹는다.
  • 양분을 먹은 나무는 나이가 1 증가한다.
  • 양분을 먹을 수 없는 나무는 즉시 죽는다.
• 여름 : 죽은 나무가 양분으로 변한다.
  • 죽은 나무마다 나이를 2로 나눈값이 나무가 있던 칸에 양분으로 추가된다.
• 가을 : 나무가 번식한다.
  • 번식하는 나무는 나이가 5의 배수이며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
• 겨울 : 양분을 추가한다.

🤔 문제분석

• 주어진 조건을 분석하여 조건에따라서 문제를 해결하면 된다.
• 나이가 작은 순서대로 순회해야함으로, 필자는 Deque 자료구조를 활용하였다.
  • 초기 나무를 입력받은 값을 나이순으로 오름차순 정렬하여 Deque에 넣었다.
  • 나이가 1인 나무가 생길때는 appendLeft를 하였다.
• 여기서 중요한점은, 서로간의 상관이 없는것들을 동일한 리터레이션에서 처리해준다.

📝 의사코드

1. 봄, 여름을 처리한다.
2. 가을, 겨울을 처리한다.
3. 봄, 여름, 가을, 겨울을 처리했으면 1년을 추가한다.
4. K년이 도달되면 멈춘다.
5. 나무의 개수를 카운팅하여 결과를 출력한다.

💻 코드

import sys
from collections import deque

nears = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

input = sys.stdin.readline

N, M, K = map(int, input().split())

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

# 양분은 5
land = [[[5, deque()] for _ in range(N+1)] for _ in range(N+1)]

tree.sort(key=lambda x:x[2])

for i, j, age in tree:
    land[i][j][1].append(age)
    
    
def spring_summer():
    dead_tree = deque()
    for i in range(1, N+1):
        for j in range(1, N+1):
            trees = land[i][j][1]
            live_tree = deque()
            for age in trees:
                if land[i][j][0] >= age:
                    land[i][j][0] -= age
                    live_tree.append(age+1)
                else:
                    dead_tree.append((i, j, age))
            land[i][j][1] = live_tree
            
    for i, j, age in dead_tree:
        land[i][j][0] += age//2

def fall_winter():
    for i in range(1, N+1):
        for j in range(1, N+1):
            trees = land[i][j][1]
            land[i][j][0] += A[i-1][j-1]
            for age in trees:
                if age % 5 == 0:
                    for dy, dx in nears:
                        ny, nx = dy + i, dx + j
                        if N >= ny >0 and N >= nx > 0:
                            land[ny][nx][1].appendleft(1)
                            
for _ in range(K):
    spring_summer()
    fall_winter()
    
ans = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        trees = land[i][j][1]
        ans += len(trees)
        
print(ans)

🎯 피드백 및 개선사항

• 없음

❓다른사람은 어떻게 풀었을까?

• 구현문제로 거의 모든사람이 동일하게 문제를 해결하였습니다.