[문제풀이-백준] 16235. 나무 재테크

풀이

개선 사항 (시간초과)

매년 시작할 때 sort를 해줬으나 처음 인풋에는 한 곳에 여러 나무가 주어지지는 않는다고 한 점을 이용했다. 이후에 추가되는 나무의 나이는 모두 1세이므로 처음 나무보단 나이가 적을 수 밖에 없다. 따라서 deque를 이용했다.

• 그래도 여전히 시간초과가 발생했고, 시간초과가 나지 않은 코드를 보면 3차원 리스트로 만들어서 거기에 나무들을 다 표시해줬다.

다시 풀어본 방법 (최종)

봄, 여름, 가을, 겨울을 함수로 나누어서 진행했다. 네이밍도 신경썼더니 처음보다 코드의 가독성이 높아졌다. 그리고 각 계절마다 요구한대로 구현했다.

• 봄
  • 양분을 먹을 수 있는 나무들은 양분을 먹고, 나이+1을 한다.
  • 양분을 먹을 수 없다면 그 나무부터 맨 뒤까지는 모두 죽을 나무이고, 이 나무들을 dead_trees에 따로 보관한다. 그리고 바로 break문을 해야한다.
• 여름
  • Dead_trees에 모아놓은 죽은 나무들만 계산해서 양분으로 바꿔준다.
• 가을
  • 처음에 5의 배수가 될때까지 나이를 먹여야하는줄 알았다. 하지만 5의 배수인 나무만 번식한다는 뜻이었다.
  • 이때 주의해야할 점이 번식된 나무는 그해에 다시 재 번식을 하면 안된다. 나는 딕셔너리의 items로 변경했기 때문에 변경되기 이전에 튜플을 반환하게된다. for문 중간에는 영향을 끼치지 않으므로 그 해에 번식된 나무는 번식 유무를 따지지 않았다.
• 겨울
  • 양분을 보충한다.

팁

딕셔너리의 items()는 key와 value를 튜플로 묶어서 반환해준다. 따라서 중간에 딕셔너리의 값을 변경해도 영향을 받지 않는다.

코드

정답 코드

def spring():
    for location, trees in live_trees.items():
        y, x = location[Y], location[X]
        for index, age in enumerate(trees):
            if field[y][x] >= age:
                field[y][x] -= age
                live_trees[location][index] = age + 1
            else:
                live = trees[:index]
                dead = trees[index:]
                live_trees[location] = live
                dead_trees[location] = dead
                break
    return

def summer(field, dead_trees):
    for location, trees in dead_trees.items():
        if not trees: continue
        y, x = location[Y], location[X]
        for age in trees:
            field[y][x] += age // 2
        dead_trees[location] = []
    return field, dead_trees

def fall(live_trees):
    def breed(y, x, live_trees):
        for dir in range(D):
            ny, nx = y + direct[dir][Y], x + direct[dir][X]
            if 0 <= ny < N and 0 <= nx < N:
                live_trees[(ny, nx)].append(1)

        return live_trees

    for location, trees in live_trees.items():
        if not trees: continue
        for age in trees:
            if age % 5: continue
            live_trees = breed(location[Y], location[X], live_trees)

    for location, trees in live_trees.items():
        if not trees: continue
        live_trees[location] = sorted(trees)
    return live_trees

def winter(field):
    for i in range(N):
        for j in range(N):
            field[i][j] += food[i][j]
    return field

def check_life_and_death(live_trees):
    cnt = 0
    for trees in live_trees.values():
        cnt += len(trees)
    return cnt

Y, X, D = 0, 1, 8
N, M, K = map(int,input().split())
food = [list(map(int,input().split())) for _ in range(N)]
treeData = [list(map(int,input().split())) for _ in range(M)]
field = [[5] * N for _ in range(N)]
live_trees = {(i,j): [] for i in range(N) for j in range(N)}
dead_trees = {(i,j): [] for i in range(N) for j in range(N)}
direct = [(-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1)]
year = 0

for y,x,z in treeData:
    live_trees[(y-1,x-1)].append(z)

for location in live_trees:
    live_trees[location] = sorted(live_trees[location])

while year < K:
    spring()
    field, dead_trees = summer(field, dead_trees)
    live_trees = fall(live_trees)
    field = winter(field)
    year += 1

answer = check_life_and_death(live_trees)
print(answer)

시간초과 코드 (42~43%)

from _collections import deque

dy=[-1,-1,0,1,1,1,0,-1]
dx=[0,1,1,1,0,-1,-1,-1]
answer = 0
N,M,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
tree = {(i,j): deque() for i in range(N) for j in range(N)}
for i in range(M):
    x, y, z = map(int,input().split())
    tree[(x-1,y-1)].append(z)
matrix = [[5] * N for _ in range(N)]
time = 0
while time < K:
    # 봄
    for k in tree.keys():
        # tree[k].sort()
        r, c = k
        survived_tree = deque()
        val = 0
        for age in tree[k]:
            if matrix[r][c] - age >= 0:
                matrix[r][c] -= age
                survived_tree.append(age+1)
            else:
                val += age // 2
        tree[k] = survived_tree
        matrix[r][c] += val
    # 여름
    # 가을
    temp = {(i,j): 0 for i in range(N) for j in range(N)}
    for k,lst in tree.items():
        for idx,age in enumerate(lst):
            if age % 5 == 0:
                r,c = k
                for dir in range(8):
                    nr,nc = dy[dir]+r,dx[dir]+c
                    if 0 <= nr < N and 0 <= nc < N:
                        n = (nr,nc)
                        temp[n] += 1
    for k,cnt in temp.items():
        for c in range(cnt):
            tree[k].appendleft(1)
    # 겨울
    for i in range(N):
        for j in range(N):
            matrix[i][j] += A[i][j]
    time += 1

for lst in tree.values():
    answer += len(lst)

print(answer)