124. [삼성기출20]Python 백준 16235 번 나무 재테크(시간 초과)

안녕하세요 코딩하는 덕구입니다.

백준 16235 번 나무 재테크 입니다.

python, pypy3시간 초과가 뜹니다. 여기서 어떻게 하면 시간을 단축 할 수 있을까요?

 

먼저 백준 16235 번 나무 재테크 시간초과 코드입니다. 설명은 아래에 있습니다.

from collections import deque
import sys
input = sys.stdin.readline

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

N, M, K = map(int, input().split())
board = [[5 for _ in range(N)] for _ in range(N)]
nutrition = [list(map(int, input().split())) for _ in range(N)]
trees = deque()
dead_trees = deque()
breeding = deque()

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

def spring():
    for i in range(len(trees)):
        x, y, age = trees.popleft()
        if age <= board[x][y]:
            board[x][y] -= age
            age += 1
            trees.append([x, y, age])
            if age % 5 == 0:
                breeding.append([x, y, age])

        else:
            dead_trees.append([x, y, age])

def summer():
    while dead_trees:
        x, y, age = dead_trees.pop()
        board[x][y] += age//2

def fall():
    while breeding:
        x, y, _ = breeding.pop()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                trees.appendleft([nx, ny, 1])

def winter():
    for i in range(N):
        for j in range(N):
            board[i][j] += nutrition[i][j]


for _ in range(K):
    spring()
    summer()
    fall()
    winter()

print(len(trees))

 

문제 접근

단순한 구현문제 입니다.

문제에서 제시한 봄, 여름, 가을, 겨울을 구현하면 됩니다.

 

Python 코드 구현

 코드를 구현하기 위해 필요한 변수들을 선언해줍니다.

from collections import deque
import sys
input = sys.stdin.readline

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

N, M, K = map(int, input().split())
board = [[5 for _ in range(N)] for _ in range(N)]
nutrition = [list(map(int, input().split())) for _ in range(N)]
trees = deque()
dead_trees = deque()
breeding = deque()

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

 

봄 : 양분이 있다면 나무의 나이를 증가시키고, 나이가 5의 배수라면 번식하는 나무에 추가합니다.

없다면 죽은 나무에 추가합니다.

def spring():
    for i in range(len(trees)):
        x, y, age = trees.popleft()
        if age <= board[x][y]:
            board[x][y] -= age
            age += 1
            trees.append([x, y, age])
            if age % 5 == 0:
                breeding.append([x, y, age])

        else:
            dead_trees.append([x, y, age])

 

여름 : 죽은 나무 리스트를 통해 양분을 추가해줍니다.

def summer():
    while dead_trees:
        x, y, age = dead_trees.pop()
        board[x][y] += age//2

 

가을 :  번식 나무 리스트를 통해 나무들을 번식시켜줍니다.

def fall():
    while breeding:
        x, y, _ = breeding.pop()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                trees.appendleft([nx, ny, 1])

 

겨울 : 로봇이 양분을 추가합니다.

def winter():
    for i in range(N):
        for j in range(N):
            board[i][j] += nutrition[i][j]

 

구현이 완료된 후 함수들을 실행시켜 줍니다.

for _ in range(K):
    spring()
    summer()
    fall()
    winter()

print(len(trees))

 

파이썬 백준 16235 번 나무 재테크 최종 코드입니다. 

from collections import deque
import sys
input = sys.stdin.readline

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

N, M, K = map(int, input().split())
board = [[5 for _ in range(N)] for _ in range(N)]
nutrition = [list(map(int, input().split())) for _ in range(N)]
trees = deque()
dead_trees = deque()
breeding = deque()

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

def spring():
    for i in range(len(trees)):
        x, y, age = trees.popleft()
        if age <= board[x][y]:
            board[x][y] -= age
            age += 1
            trees.append([x, y, age])
            if age % 5 == 0:
                breeding.append([x, y])

        else:
            dead_trees.append([x, y, age])

def summer():
    while dead_trees:
        x, y, age = dead_trees.pop()
        board[x][y] += age//2

def fall():
    while breeding:
        x, y = breeding.pop()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                trees.appendleft([nx, ny, 1])

def winter():
    for i in range(N):
        for j in range(N):
            board[i][j] += nutrition[i][j]


for _ in range(K):
    spring()
    summer()
    fall()
    winter()

print(len(trees))

 

백준 16235 번 나무 재테크 시간초과 Python 코드였습니다.

감사합니다.