16235 - 나무재테크

하... 이 문제는 39번 시도 끝에 통과한 문제다.

 

극히 일부만 캡쳐했지만 하다하다 오기가 생겨서 계속 시도하다 보니 이렇게까지 제출 횟수가 늘어났던것 같다.

42%에서 시간초과가 계속 나오는 것을 보고 이래저래 고치다보니 틀렸습니다가 나오기는 했지만 ㅎㅎㅎ

그래도 다양한 반례를 테스트 해보면서 로직상의 문제는 크게 없다는 것을 깨달았다. 시간초과가 문제였을 뿐...

 

어쨌든 하다가 너무 짜증나서 다른 사람의 풀이를 봐야지 하다가 하나의 차이점을 발견했다.

copyTreeAge =deepcopy(treeAge[nr][nc])
copyTreeAge.appendleft(1)
treeAge[nr][nc] = copyTreeAge

나는 위의 코드처럼 깊은 복사를 해주어야만 appendleft를 해도 treeAge[nr] 리스트 전체에 append되지 않았다.

즉 treeAge = [[1, 2, 3], [1, 2, 3], [1, 2, 3]]이라 했을 때,

깊은 복사를 하지 않고 appendleft를 하게 되면 [[1, 1, 2, 3], [1, 1, 2, 3], [1, 1, 2, 3]]이 되는 것이다.

 

그런데 다른 사람의 코드에는 굳이 깊은 복사를 하지 않아도 appendleft를 했을 때 정답으로 이어지는 것이다. 

 

그래서 불현듯 처음에 내가 정의한 treeAge를 보았다.

treeAge = [[deque([])] * N for _ in range(N)]

위와 같이 정의가 되어있었다. 

 

이렇게 되면 배열안에 배열을 선언하는 것이 아니라 배열 안의 모든 배열을 선언하게 되는 것이다. 그러다 보니 2차원 좌표가 아닌 모든 배열을 선언하게 되어 같은 값을 넣게 된 것이었다. 

 

그래서 다음과 같이 treeAge를 재정의 하고나서 확인해보니 테스트를 통과할 수 있었다...

treeAge = [[deque() for _ in range(N)] for _ in range(N)]

아래는 통과한 소스코드이다.

# 봄 : 자신의 나이만큼 양분을 먹고, 나이가 1 증가
# -> 하나의 칸에 여러개의 양분이 있다면, 나이가 어린 나무부터 양분을 먹는다.
# -> 양분이 부족해 자신의 나이만큼 먹을 수 없는 나무는 양분을 먹지 못하고 죽는다.
# 여름 : 봄에 죽은 나무가 양분으로 변하게 된다. : 죽은 나무마다 나이/2 값이 나무가 있던 칸에 양분으로 추가
def springSummer(treeAge, land):
    for i in range(N):
        for j in range(N):
            if len(treeAge[i][j]) > 0:
                nutrient = land[i][j]; ta = treeAge[i][j]
                liveTa = deque([]); tmpNutrient = 0
                for k in range(len(ta)):
                    if nutrient >= ta[k]:
                        nutrient -= ta[k]
                        liveTa.append(ta[k]+1)
                    else:
                        tmpNutrient += (ta[k] // 2)

                treeAge[i][j] = liveTa
                land[i][j] = (nutrient + tmpNutrient)
    return treeAge, land


# 가을 : 나이가 5의 배수이면 번식 (인접한 8개의 칸에 나이가 1인 나무가 생김)
# 겨울 : S2D2가 땅을 돌아다니면서 땅에 양분을 추가
def fallWinter(treeAge, land):
    dx = [-1, -1, -1, 0, 0, 1, 1, 1]
    dy = [-1, 0, 1, -1, 1, -1, 0, 1]
    for r in range(N):
        for c in range(N):
            # 가을
            for age in treeAge[r][c]:
                if age % 5 == 0:
                    for i in range(8):
                        nr = r + dx[i]; nc = c + dy[i]
                        if 0 <= nr < N and 0 <= nc < N:
                            treeAge[nr][nc].appendleft(1)

            # 겨울
            land[r][c] += S2D2land[r][c]

    return treeAge, land

from collections import deque
from copy import deepcopy
if __name__ == '__main__':
    N, M, K = map(int, input().split())
    land = [[5] * N for _ in range(N)]

    # 각 칸의 양분
    S2D2land = []
    for _ in range(N):
        temp = list(map(int, input().split()))
        S2D2land.append(temp)

    # 각 칸에 존재하는 나무의 나이
    treeAge = [[deque() for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        x, y, z = map(int, input().split())
        treeAge[x - 1][y - 1].append(z)

    for k in range(K):
        treeAge, land = springSummer(treeAge, land)
        treeAge, land = fallWinter(treeAge, land)

    result = 0
    for i in range(N):
        for j in range(N):
            result += len(treeAge[i][j])

    print(result)