[백준] 16235번 (python 파이썬)

https://www.acmicpc.net/problem/16235

 

구현, 시뮬레이션 문제이다.

시간제한을 보면

파이썬은 1.3초안에 통과해야한다... 엄청 빡세다..

 

사실 알고리즘은 필요로 하지 않는 문제이다.

 

하지만 시간초과로인해 고려해야 할 점이 많았다.

 

처음 접근한 방식은 나무에 대한 좌표와 나이를 묶어서 deque에 넣으면서 확인을 하였다.

 

from collections import deque

n, m, k = map(int, input().split(' '))

a = [list(map(int, input().split(' '))) for _ in range(n)]
graph = [[5] * n for _ in range(n)]
trees = deque()  #나무들이 들어있는 deque
dead_trees = list()
for _ in range(m):
    x, y, z = map(int, input().split(' '))
    trees.append([z, x, y])

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


def spring_summer():
    len_ = len(trees)
    for _ in range(len_):
        z, x, y = trees.popleft()
        if graph[x - 1][y - 1] < z:
            dead_trees.append([z, x, y])
        else:
            graph[x - 1][y - 1] -= z
            trees.append([z + 1, x, y])
            
    while dead_trees:
        z, x, y = dead_trees.pop()
        graph[x - 1][y - 1] += z // 2


def fall_winter():
    for z, x, y in list(trees):
        if z % 5 == 0:
            for i in range(8):
                nx, ny = x + dx[i] - 1, y + dy[i] - 1

                if nx < 0 or nx >= n or ny < 0 or ny >= n:
                    continue

                trees.appendleft([1, nx + 1, ny + 1])
                
    for i in range(n):
        for j in range(n):
            graph[i][j] += a[i][j]
    


for i in range(k):
    spring_summer()
    fall_winter()

print(len(trees))

 

deque 는 append 와 pop 이 모두 O(1)이어서 왜 계속 시간 초과가 나는지 몰랐다....

시간초과가 어디에서 나는지 모르겠지만 

양분이 없을때 나무를 제거할때 나는 것같다.

그래서

양분이 없을때 즉시 해당 좌표에 있는 나무들을 모두 제거해줬다.

 

최종 코드

from collections import deque

n, m, k = map(int, input().split(' '))

a = [list(map(int, input().split(' '))) for _ in range(n)]
graph = [[5] * n for _ in range(n)]
trees = [[deque() for _ in range(n)] for _ in range(n)]
dead_trees = [[list() 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)

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


def spring_summer():
    for i in range(n):
        for j in range(n):
            len_ = len(trees[i][j])
            for k in range(len_):
                if graph[i][j] < trees[i][j][k]:
                    for _ in range(k, len_):
                        dead_trees[i][j].append(trees[i][j].pop())
                    break
                else:
                    graph[i][j] -= trees[i][j][k]
                    trees[i][j][k] += 1

    for i in range(n):
        for j in range(n):
            while dead_trees[i][j]:
                graph[i][j] += dead_trees[i][j].pop() // 2


def fall_winter():
    for i in range(n):
        for j in range(n):
            for k in range(len(trees[i][j])):
                if trees[i][j][k] % 5 == 0:
                    for l in range(8):
                        nx, ny, = i + dx[l], j + dy[l]

                        if nx < 0 or nx >= n or ny < 0 or ny >= n:
                            continue
                        trees[nx][ny].appendleft(1)

            graph[i][j] += a[i][j]


for i in range(k):
    spring_summer()
    fall_winter()

answer = 0
for i in range(n):
    for j in range(n):
        answer += len(trees[i][j])

print(answer)