문제 링크
https://www.acmicpc.net/problem/16235
🕒 Python 풀이시간: 40분
from collections import deque
import copy
n,m,k=map(int,input().split())
a=[[5]*n for _ in range(n)]
plus_a=[list(map(int,input().split())) for _ in range(n)]
trees=[[deque() for _ in range(n)] for _ in range(n)]
for _ in range(m):
x,y,z=map(int,input().split())
trees[x-1][y-1].append(z)
for i in range(n):
for j in range(n):
tmp=list(trees[i][j])
tmp.sort()
trees[i][j]=deque(tmp)
dx=[0,0,-1,1,-1,-1,1,1]
dy=[-1,1,0,0,1,-1,1,-1]
for _ in range(k):
new_trees_cnt=[[0]*n for _ in range(n)]
for i in range(n):
for j in range(n):
now_trees=trees[i][j]
died_trees_a=0
died_index=-1
for t in range(len(now_trees)):
if a[i][j]>=now_trees[t]:
a[i][j]-=now_trees[t]
now_trees[t]+=1
if now_trees[t]%5==0 and now_trees[t]!=0:
for d in range(8):
nx=i+dx[d]
ny=j+dy[d]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
new_trees_cnt[nx][ny]+=1
else:
died_trees_a+=now_trees[t]//2
if died_index==-1:
died_index=t
if died_index>=0:
trees[i][j]=deque(list(now_trees)[:died_index])
a[i][j]+=died_trees_a
for i in range(n):
for j in range(n):
trees[i][j].extendleft([1]*new_trees_cnt[i][j])
a[i][j]+=plus_a[i][j]
answer=0
for i in range(n):
for j in range(n):
answer+=len(trees[i][j])
print(answer)🌳 나무 재테크의 계절 변화 🍂
처음 모든 칸에 양분이 5씩 있고 1년을 주기로 나무 재테크를 위해 나무의 수를 파악하는 문제이다. 봄에는 각 칸에 있는 나무가 어린 순으로 각 나이만큼 양분을 먹고 한살을 더 먹는다. 자신의 나이만큼 양분을 먹지 못한 나무는 죽어 여름에 자신의 나이를 2로 나눈 값만큼 양분으로 전환된다. 가을에는 나이가 5의 배수인 나무의 주위 8칸에 1인 나무가 생긴다. 겨울에는 각 칸에 주어진 a만큼의 양분이 증가한다.
각 나무는 나이로 관리하기 위해 각 칸을 큐로 두었다. 이는 1인 나무가 추가될 때, 어린 순으로 나중에 계산할 것을 생각해서 앞쪽에 나무를 넣기 위함이다. 모든 칸을 순회하면서 나무를 찾으며 해당 큐를 앞에서부터 즉, 어린 순으로 순회하면서 나이 만큼 양분을 줄이고 나이를 먹는다. 만약 양분이 부족하면 해당 나무를 죽인다. 이 때 처음 죽는 나무의 index를 기억해두었다가 나중에 배열을 슬라이스로 넣어서 한번에 죽은 나무를 뺀다. 이는 나이순으로 되어있기 때문에 앞의 나무가 죽을 경우, 뒤의 나무는 계산할 필요없이 죽기 때문이다. 이 때 여름을 한꺼번에 처리하기 위해 죽은 나무의 양분을 전환하여 더해두었다가 해당칸의 모든 나무의 순회가 끝나면 더해준다. 이와 동시에 나무가 나이가 먹는 순간에 해당 나무의 나이가 5의 배수라면 주위 8칸에 1인 나무를 cnt해둔다. 이 때, 동시성이 적용되기 때문에 따로 세어 놨다가 더해야한다.
이제 가을까지 처리하기 위해 이중 포문으로 탐색이 끝나면 다시 이중포문으로 추가된 나무를 더해준다. 이와 같이 겨울까지 처리하기 위해 각 칸에 a만큼의 양분을 더해주면 된다.
이렇게 Python로 백준의 "나무 재테크" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
