[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