[Python] 16235. 나무 재테크

www.acmicpc.net/problem/16235

16235번: 나무 재테크

---

시간초과 (0%)

def spring(x,y,z):
​​​​if ground[x][y] < z:
​​​​​​​​z = -z #사망
​​​​else:
​​​​​​​​ground[x][y] -= z
​​​​​​​​z += 1
​​​​return x,y,z

def summer(x,y,z):
​​​​if z < 0:
​​​​​​​​ground[x][y] += abs(z)//2

def fall(x,y,z):
​​​​global N
​​​​child = []
​​​​for i in range(len(direction)):
​​​​​​​​next_x = x + direction[i][0]
​​​​​​​​next_y = y + direction[i][1]
​​​​​​​​if 0<=next_x<N and 0<=next_y<N:
​​​​​​​​​​​​child.append((next_x,next_y,1))
​​​​return child

def winter():
​​​​global N
​​​​for r in range(N):
​​​​​​​​for c in range(N):
​​​​​​​​​​​​ground[r][c] += A[r][c]

def solve(queue,K):
​​​​year = 0
​​​​while True:
​​​​​​​​if year == K:
​​​​​​​​​​​​return len(queue)
​​​​​​​​alive = []
​​​​​​​​dead = []
​​​​​​​​while queue:
​​​​​​​​​​​​x,y,z = queue.pop(0)
​​​​​​​​​​​​_x,_y,_z = spring(x,y,z)
​​​​​​​​​​​​if _z < 0:
​​​​​​​​​​​​​​​​dead.append((_x,_y,_z))
​​​​​​​​​​​​​​​​continue
​​​​​​​​​​​​alive.append((_x,_y,_z))

​​​​​​​​while dead:
​​​​​​​​​​​​x,y,z = dead.pop(0)
​​​​​​​​​​​​summer(x,y,z)

​​​​​​​​for a in alive:
​​​​​​​​​​​​x,y,z = a
​​​​​​​​​​​​if z % 5 == 0:
​​​​​​​​​​​​​​​​queue.extend(fall(x,y,z))

​​​​​​​​winter()
​​​​​​​​queue.extend(alive)
​​​​​​​​year += 1

​​​​return queue


direction = ((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))

N,M,K = map(int, input().split())
ground = [[5]*N for _ in range(N)]
A = [list(map(int, input().split())) for _ in range(N)]
queue = []

for _ in range(M):
​​​​x,y,z = map(int, input().split())
​​​​queue.append([x-1,y-1,z])

# 입력으로 주어지는 나무의 위치는 모두 서로 다르므로 초기 정렬 불필요
# queue = sorted(queue, key=lambda q:q[2])
answer = solve(queue,K)

print(answer)

 

시간초과 (47%)

from collections import deque

def solve():
​​​​global N,K
​​​​year = 0

​​​​while year != K:
​​​​​​​​# 봄
​​​​​​​​for x in range(N):
​​​​​​​​​​​​for y in range(N):
​​​​​​​​​​​​​​​​while tree[x][y]:
​​​​​​​​​​​​​​​​​​​​z = tree[x][y].popleft()
​​​​​​​​​​​​​​​​​​​​if z > ground[x][y]:
​​​​​​​​​​​​​​​​​​​​​​​​dead[x][y].append(z)
​​​​​​​​​​​​​​​​​​​​​​​​continue
​​​​​​​​​​​​​​​​​​​​ground[x][y] -= z
​​​​​​​​​​​​​​​​​​​​alive[x][y].append(z+1)

​​​​​​​​for x in range(N):
​​​​​​​​​​​​for y in range(N):
​​​​​​​​​​​​​​​​# 여름
​​​​​​​​​​​​​​​​while dead[x][y]:
​​​​​​​​​​​​​​​​​​​​ground[x][y] += dead[x][y].pop()//2
​​​​​​​​​​​​​​​​# 가을
​​​​​​​​​​​​​​​​for age in alive[x][y]:
​​​​​​​​​​​​​​​​​​​​if age % 5 == 0:
​​​​​​​​​​​​​​​​​​​​​​​​for i in range(len(direction)):
​​​​​​​​​​​​​​​​​​​​​​​​​​​​next_x = x + direction[i][0]
​​​​​​​​​​​​​​​​​​​​​​​​​​​​next_y = y + direction[i][1]
​​​​​​​​​​​​​​​​​​​​​​​​​​​​if 0 <= next_x < N and 0 <= next_y < N:
​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​alive[next_x][next_y].appendleft(1)
​​​​​​​​​​​​​​​​# 겨울
​​​​​​​​​​​​​​​​ground[x][y] += A[x][y]

​​​​​​​​for x in range(N):
​​​​​​​​​​​​for y in range(N):
​​​​​​​​​​​​​​​​if alive[x][y]:
​​​​​​​​​​​​​​​​​​​​tree[x][y].extend(alive[x][y])
​​​​​​​​​​​​​​​​​​​​alive[x][y] = deque()

​​​​​​​​year += 1

direction = ((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))

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

tree = [[deque() for _ in range(N)] for _ in range(N)]
alive = [[deque() for _ in range(N)] for _ in range(N)]
dead = [[deque() for _ in range(N)] for _ in range(N)]

for _ in range(M):
​​​​x,y,z = map(int, input().split())
​​​​tree[x-1][y-1].append(z)

solve()

answer = 0
for x in range(N):
​​​​for y in range(N):
​​​​​​​​if tree[x][y]:
​​​​​​​​​​​​answer += len(tree[x][y])

print(answer)

 

통과: 100%

메모리: 139664KB

시간: 712ms

 

봄여름을 동시에 처리하여 통과

 

from collections import deque

def solve():
​​​​global N,K
​​​​year = 0
​​​​while year != K:
​​​​​​​​# 봄 & 여름
​​​​​​​​for x in range(N):
​​​​​​​​​​​​for y in range(N):
​​​​​​​​​​​​​​​​tmp = 0
​​​​​​​​​​​​​​​​alive = deque()
​​​​​​​​​​​​​​​​while tree[x][y]:
​​​​​​​​​​​​​​​​​​​​z = tree[x][y].popleft()
​​​​​​​​​​​​​​​​​​​​if z > ground[x][y]:
​​​​​​​​​​​​​​​​​​​​​​​​tmp += z // 2
​​​​​​​​​​​​​​​​​​​​else:
​​​​​​​​​​​​​​​​​​​​​​​​ground[x][y] -= z
​​​​​​​​​​​​​​​​​​​​​​​​alive.append(z+1)
​​​​​​​​​​​​​​​​ground[x][y] += tmp
​​​​​​​​​​​​​​​​tree[x][y] = alive

​​​​​​​​for x in range(N):
​​​​​​​​​​​​for y in range(N):
​​​​​​​​​​​​​​​​# 가을
​​​​​​​​​​​​​​​​for age in tree[x][y]:
​​​​​​​​​​​​​​​​​​​​if age % 5 == 0:
​​​​​​​​​​​​​​​​​​​​​​​​for i in range(len(direction)):
​​​​​​​​​​​​​​​​​​​​​​​​​​​​next_x = x + direction[i][0]
​​​​​​​​​​​​​​​​​​​​​​​​​​​​next_y = y + direction[i][1]
​​​​​​​​​​​​​​​​​​​​​​​​​​​​if 0 <= next_x < N and 0 <= next_y < N:
​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​tree[next_x][next_y].appendleft(1)
​​​​​​​​​​​​​​​​# 겨울
​​​​​​​​​​​​​​​​ground[x][y] += A[x][y]
​​​​​​​​year += 1

# 초기화
direction = ((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))
N,M,K = map(int, input().split())
ground = [[5]*N for _ in range(N)]
A = [list(map(int, input().split())) for _ in range(N)]
tree = [[deque() for _ in range(N)] for _ in range(N)]
for _ in range(M):
​​​​x,y,z = map(int, input().split())
​​​​tree[x-1][y-1].append(z)

# main
solve()

# 결과출력
answer = 0
for x in range(N):
​​​​for y in range(N):
​​​​​​​​if tree[x][y]:
​​​​​​​​​​​​answer += len(tree[x][y])
print(answer)

 

문제를 푸는데 도움이 된 테스트 케이스

# Input 5 2 7 2 3 2 3 2 2 3 2 3 2 2 3 2 3 2 2 3 2 3 2 2 3 2 3 2 2 1 3 3 2 3 # Output 71