[Python]16235. 나무 재테크

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

16235번: 나무 재테크

---

 

이 문제는 시뮬레이션 문제로 문제를 분석해서 코드를 짜는데 크게 어렵진 않았다.

다만 나무를 1차원 리스트로 통째로 관리해서 푼다면

데이터가 커질때 정렬하는 과정에서 어마어마하게 시간이 오래 걸리게 된다.

heapq를 사용한다고 해도 시간초과가 발생하므로, 

나무를 3차원 배열을 만든다음 2차원 평면에서 나무의 수를 1차원 리스트로 관리하는것이 시간초과를 방지할 수 있다.

 

 

def print_year(cnt, ground, tree):
    print("****** YEAR: {} ******".format(cnt))
    for i in range(len(ground)):
        print("{}\t\t{}".format(ground[i], tree[i]))
    print()
 
def main():
    global doPrint
    n, m, k = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    tree = [[[] for _ in range(n)] for _ in range(n)]
    for _ in range(m):
        y,x,z = map(int, input().split())
        tree[y-1][x-1].append(z)
    ground = [[5]*n for _ in range(n)]
    direction = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
    cnt = 0
 
    if doPrint:
        print_year(cnt, ground, tree)
 
    while cnt != k:
 
        # 봄 & 여름
        for i in range(n):
            for j in range(n):
                if tree[i][j]:
                    dead = []
                    alive = []
 
                    # 봄
                    tree[i][j].sort()
                    while tree[i][j]:
                        yrs = tree[i][j].pop(0)
                        if ground[i][j] < yrs:
                            dead.append(yrs)
 
                        else:
                            ground[i][j] -= yrs
                            yrs += 1
                            alive.append(yrs)
                    tree[i][j].extend(alive)
 
                    #여름
                    while dead:
                        yrs = dead.pop(0)
                        ground[i][j] += (yrs // 2)
 
        #가을
        for i in range(n):
            for j in range(n):
                tr = tree[i][j][:]
                for yrs in tr:
                    if yrs % 5 == 0:
                        for d in direction:
                            ny, nx = i + d[0], j + d[1]
                            if 0 <= ny < n and 0 <= nx < n:
                                tree[ny][nx].append(1)
 
        # 겨울
        for i in range(n):
            for j in range(n):
                ground[i][j] += a[i][j]
 
        cnt += 1
 
        if doPrint:
            print_year(cnt, ground, tree)
 
    ans = 0
    for i in range(n):
        for j in range(n):
            ans += len(tree[i][j])
    print(ans)
 
if __name__=="__main__":
    doPrint = False # True 시 year마다 출력
    main()