[백준/16235/파이썬] 나무 제테크

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

16235번: 나무 재테크

Problem

• 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 
• K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하는 프로그램을 작성하시오.

조건

• 가장 처음에 양분은 모든 칸에 5만큼 들어있다.
• 봄 : 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
• 여름 : 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
• 가을 : 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 어떤 칸 (r, c)와 인접한 칸은 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1) 이다. 상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.
• 겨울: S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.

SOL

시뮬레이션 문제이다. 봄~ 겨울을 구현하고, 살이있는 나무를 구하면 된다.

 

2개의 board를 이용 

• 한 개의 board내에 비료/나무를 다 기록해도되지만,  한 땅(칸)에 여러개의 나무가 있을 수 있기 때문에, 나무는 다른 board에 구현하는게 좋아보인다. 즉, 땅 board와 나무 board 2개로 구현할 거다.
• 그리고, 여러개의 나무가 한 땅에 있을 수 있으므로, 나무는 3차원 배열 느낌으로, 2차원 board인데, deque를 갖고있는 board로 구현을 할거다.
• 작은 나무가 먼저 양분을 흡수하기 때문에, 나무가 번식할 때, appendleft를 해줘서, 순서를 맞춰줄거임.

계절 구현

• 봄/여름은 합쳐서 구현해도 무방할거 같다. 나무가 양분을 먹을수 있냐/없냐에 따라서 처리를 해줘야하기 때문이다.
• 가을/겨울 또한, 가을은 tree_board를 update하는 과정이고, 겨울은 땅 board에 다시 양분을 주는 과정이므로, 따로 구현하기 보다는, 한꺼번에 묶어서 구현해도 될듯하다.

# 나무 재테크
import sys
from collections import deque
input= sys.stdin.readline

N,M,K = map(int,input().split())
S2D2=[list(map(int,input().split())) for _ in range(N)]
tree_board=[[deque() for _ in range(N)] for _ in range(N)]
food_board=[[5 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a,b,c= map(int,input().split())
    tree_board[a-1][b-1].append(c)

def spring():
    for i in range(N):
        for j in range(N):
            alive_tree=len(tree_board[i][j])
            for k in range(alive_tree):
                # 비료가 충분한 경우
                if tree_board[i][j][k]<=food_board[i][j]:
                    food_board[i][j] -= tree_board[i][j][k]
                    tree_board[i][j][k] +=1
                # 나무가 죽는 경우 (여름)
                # 양분이 부족한 나무들은 싹 다 죽어서 양분이 된다.
                # 나이가 어린 나무가 앞에 있기 때문에, 이렇게 처리함.
                else:
                    for _ in range(k,alive_tree):
                        food_board[i][j] += tree_board[i][j].pop()//2
                    break

def autumn():
    dx=[0,1,0,-1,1,1,-1,-1]
    dy=[1,0,-1,0,1,-1,1,-1]
    for i in range(N):
        for j in range(N):
            for z in tree_board[i][j]:
                if z%5==0:
                    for k in range(8):
                        ny=i+dy[k]
                        nx=j+dx[k]
                        if 0<=ny<N and 0<=nx<N:
                            tree_board[ny][nx].appendleft(1)
            #비료를 나타내는 board와 tree가 있는 board는 독립적이고, 가을에는, 비료에 대한 시행이 없음.
            # 가을 + 겨울을 같이 나타내자 그냥.
            food_board[i][j] += S2D2[i][j]

while K:
    spring()
    autumn()
    K-=1
ans=0
for i in range(N):
    for j in range(N):
        ans+=len(tree_board[i][j])

print(ans)