[백준] 16235(파이썬) - 나무 제테크

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

16235번: 나무 재테크

 

• 하라는 대로 하면 되는 삼성 기출문제 유형의 문제였지만, 시간 초과가 있어 상당히 까다로웠습니다. 처음에 푼 방식에서 테스트 케이스를 모두 통과했지만 시간 초과가 발생했고, 로직은 유지하면서 시간 초과를 어떻게 줄일 수 있을지 고민했습니다. 
  시간이 정말 오래걸렸는데요, 문제를 맞았을 때 쾌감이 어마어마했던 문제입니다.
• 먼저 하라는대로 하면 되는 구현 문제는 문제를 잘 읽어야 합니다. 저 같은 경우에는 처음에 양분 그래프를 5로 초기화했어야 했는데 문제를 잘못 읽어서 입력받은 양분 값들로 초기화를 해서 30분은 잡아먹었습니다.
• 봄, 여름, 가을, 겨울 조건을 잘 읽고 구현을 해주면 됩니다.
• 처음 문제를 풀 때는 일차원 배열 2개를 이용해서 deque로 바꾸고, 시간을 아끼기 위해 popleft를 사용해서 가장 나이가 어린 나무한테 접근했는데요, 결국에는 deque를 사용하지 않고, 3차원 배열을 만들어서 풀었습니다. 따지고 보면 2차원 배열에 리스트가 들어간 형태이죠.
• 자세한 설명은 주석을 참고해주시면 감사하겠습니다.
• 첫 번째 코드가 정답코드, 두 번째 코드가 제가 시간 초과가 났던 코드입니다. 두 코드를 비교해가면서 어떻게 변경해서 시간을 줄였는지 보시는 것도 좋을 것 같네요.

 

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

# 양분 그래프 n x n , m나무개수, k년이 지난 후
n,m,k = map(int,input().split())

# 나중에 겨울에 양분 추가해줄 그래프  = plus_soil
plus_soil = []
for _ in range(n):
    plus_soil.append(list(map(int,input().split())))

# 나무 양분 그래프
origin_soil = [[5]*n for _ in range(n)]


# 살아있는 나무 그래프
live = [[[] for _ in range(n)] for _ in range(n)]
for _ in range(m):
    x,y,z = map(int,input().split())
    live[x-1][y-1].append(z)

for _ in range(k):
    # 봄 + 여름
    for i in range(n):
        for j in range(n):
            if live[i][j] :
                # 봄에 나이가 어린 나무 부터 양분을 먹게하기위한 정렬
                live[i][j].sort()
                # live = [] # 살아있는 나무들 리스트를 알아야 가을에 번식을 할 수 있다.
                tmp_live_tree=[]
                death = 0
                for age in live[i][j]:
                    if age <= origin_soil[i][j]:
                        origin_soil[i][j] -= age
                        age += 1
                        tmp_live_tree.append(age)
                    else:
                        death += age // 2
                origin_soil[i][j] += death
                # 죽은건 죽은대로, 산건 산거대로 옮긴다.
                live[i][j] .clear()
                live[i][j].extend(tmp_live_tree)

    #가을
    dx = [-1,-1,0,1,1,1,0,-1]
    dy = [0,1,1,1,0,-1,-1,-1]

    for i in range(n):
        for j in range(n):
            if live[i][j]:
                for age in live[i][j]:
                    if age % 5 == 0:
                        for dir in range(8):
                            nx = i+ dx[dir]
                            ny = j+ dy[dir]
                            if 0<= nx < n and 0<= ny < n:
                                live[nx][ny].append(1)
    #겨울
    for i in range(n):
        for j in range(n):
            origin_soil[i][j] += plus_soil[i][j]

result = 0
for i in range(n):
    for j in range(n):
        result += len(live[i][j])
print(result)

 

 

시간 초과 코드

 

 

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

# 양분 그래프 n x n , m나무개수, k년이 지난 후
n,m,k = map(int,input().split())
# 나무 양분 그래프
plus_soil = []
for _ in range(n):
    plus_soil.append(list(map(int,input().split())))

origin_soil = [[5]*n for _ in range(n)]
# 나중에 겨울에 양분 추가해줄 그래프  = plus_soil

# 살아있는 나무 그래프
live = []
for _ in range(m):
    x,y,z = map(int,input().split())
    live.append((x-1,y-1,z))

# 봄에 나이가 어린 나무 부터 양분을 먹게하기위한 정렬



# live = [] # 살아있는 나무들 리스트를 알아야 가을에 번식을 할 수 있다.
for _ in range(k):
    live.sort(key=lambda x:(x[0],x[1],x[2]))
    death = [] # 양분못먹어서 죽은 나무들의 좌표를 넣어두는 리스트
    spring_q = deque(live)
    # 봄
    while spring_q:
        tree_x,tree_y,tree_age = spring_q.popleft()
            # 양분 먹을 때
        if origin_soil[tree_x][tree_y] >=  tree_age:
            origin_soil[tree_x][tree_y] -= tree_age
            live.remove((tree_x,tree_y,tree_age))
            live.append((tree_x,tree_y,tree_age+1))
            # 양분 못먹을 떄
        else:
            death.append((tree_x,tree_y,tree_age))
            live.remove((tree_x,tree_y,tree_age))
            
    #여름
    # print("d",death)
    summer_q = deque(death)
    while summer_q:
        death_x,death_y,death_age = summer_q.popleft()
        origin_soil[death_x][death_y] += death_age // 2

    #가을
    dx = [-1,-1,0,1,1,1,0,-1]
    dy = [0,1,1,1,0,-1,-1,-1]

    fall_q = deque(live)
    # print("fall_q",fall_q)

    while fall_q:
        live_x,live_y,live_age = fall_q.popleft()
        if live_age % 5 == 0:
            for i in range(8):
                nx = live_x + dx[i]
                ny = live_y + dy[i]
                if 0<= nx < n and 0<= ny < n:
                    live.append((nx,ny,1))
    #겨울
    for i in range(n):
        for j in range(n):
            origin_soil[i][j] += plus_soil[i][j]

print(len(live))