http://boj.kr/16235
각 계절별로 아래와 같은 행위를 정의한 다음 함수로 만들고 k년마다 실행하면 된다.
봄: 각 칸에 있는 나무들이 양분을 섭취하거나 죽은 나무 리스트에 추가된다.
여름: 죽은 나무들이 그 나이의 절반만큼 양분으로 추가된다.
가을: 어떤 나무의 나이가 5의 배수라면, 인접한 8칸에 1의 나이를 가진 나무들이 추가된다.
겨울: 모든 나무들에게 각기 주어진 만큼의 양분을 추가한다.
각 계절별로 따로 함수를 만들어도 되지만 가을, 겨울은 서로 영향을 주지 않기 때문에 하나의 반복문 내에서 실행되도록 했다.
53번줄처럼 밭을 board[N][N]으로,
1x1 크기의 각 칸은 [양분, [그 칸에 있는 나무들의 나이], 죽은 나무 나이/2, 나무의 숫자]로 정해주었고
각 칸의 인덱스를 0~3으로 접근하면 헷갈리기 때문에 MEAL, TREE, DEAD, NUM = 0, 1, 2, 3으로 define해주었다.
nutrition이 아니라 meal인 이유는 nutrition은 너무 길기 때문에...
위에서 설명한 것처럼 board 배열을 3차원으로 초기화하려면 주의해야할 것이 있다.
보통 2차원 배열을 초기화할 때 [0] * N for _ in range(N) 이라는 방법을 쓴다.
나는 여기서 [0] -> [양분, [그 칸에 있는 나무들의 나이], 죽은 나무 나이/2, 나무의 숫자] 라고 생각해서
단순히 [[[양분, [그 칸에 있는 나무들의 나이], 죽은 나무 나이/2, 나무의 숫자]] * N for _ in range(N)] for _ in range(N)]이라고 해주었었다. 문제가 되는 부분은 볼드처리 된 부분으로, 저것은 배열이기 때문에 * N 으로 만들면 안 된다! 저렇게 하면 하나의 배열 객체가 만들어진후에 N 개만큼 자가증식한다. 하나가 바뀌면 N 개의 형제들이 모두 값이 바뀌게 된다. shallow copy인 셈이다.
파이썬은 1.3초의 시간을 주긴 하지만, 기본적으로 0.3초의 시간 밖에 주지 않아서 시간을 최대한 줄이기 위해 deque를 썼다. 작은 나무 먼저 양분을 먹는다고 했으므로, 우선 입력을 받은 후에 나무 배열을 sort()로 정렬한다.
그 이후에 나무들을 차례대로 보면서 양분을 먹이거나 죽이거나 하는 과정은
28번줄에서 popleft로 맨 앞에 있는 가장 어린 나무를 꺼낸 후
31번째줄에서 맨 뒤에 다시 추가시켜 주는 식으로 반복했다. 이것을 나무의 갯수(NUM)만큼 진행하면 된다.
매번 새로 정렬해야했다면 spring()에서만 시간이 2배로 걸렸을 것이다.
import sys
from collections import deque
def fall_and_winter():
for i in range(N):
for j in range(N):
for t in board[i][j][TREE]:
if t % 5 == 0:
for d in range(8):
if 0 <= i + dx[d] < N and 0 <= j + dy[d] < N:
board[i+dx[d]][j+dy[d]][TREE].appendleft(1)
board[i+dx[d]][j+dy[d]][NUM] += 1
board[i][j][MEAL] += new_meal[i][j]
def summer():
for i in range(N):
for j in range(N):
board[i][j][MEAL] += board[i][j][DEAD]
board[i][j][DEAD] = 0
def spring():
for i in range(N):
for j in range(N):
for _ in range(board[i][j][NUM]):
tree_year = board[i][j][TREE].popleft()
if tree_year <= board[i][j][MEAL]: # 작거나 같으면 양분 섭취 가능
board[i][j][MEAL] -= tree_year # 나이만큼 양분 빼기
board[i][j][TREE].append((tree_year+1))
else: # dead
board[i][j][DEAD] += tree_year // 2
board[i][j][NUM] -= 1
def solve():
for k in range(K):
spring()
summer()
fall_and_winter()
ret = 0
for i in range(N):
for j in range(N):
ret += board[i][j][NUM]
return ret
MEAL, TREE, DEAD, NUM = 0, 1, 2, 3
input = sys.stdin.readline
N, M, K = map(int, input().split())
board = [[[5, [], 0, 0] for _ in range(N)] for _ in range(N)] # meal, trees(ages), num, dead
new_meal = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
for _ in range(M):
x, y, z = map(int, input().split())
board[x-1][y-1][TREE].append(z) # tree 추가
for i in range(N):
for j in range(N):
board[i][j][TREE] = deque(sorted(board[i][j][TREE]))
board[i][j][NUM] = len(board[i][j][TREE])
print(solve())
