[구현] 백준 16235 : 나무 재테크 - 파이썬 Python

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

16235번: 나무 재테크

생각하기

각 칸에 나무가 있고 

봄, 여름, 가을, 겨울에 따라 각 칸에 대한 이벤트를 수행

 

시간복잡도

최대 1000년이므로

1000년동안 N*N의 칸을 돌아다닐 예정

N의 최대는 10이므로 100개의 칸을 돌아다닌다

각 칸에서는 최대 100개의 나무가 있을수 있다

1000 * 100 * 100 < 10^9이므로 충분히 시간 복잡도 안에 해결 가능

 

N, M, K = map(int, input().split())

A = []
nut = [[5]*N for _ in range(N)]
for i in range(N):
    A.append(list(map(int, input().split())))

trees = [[] for _ in range(N*N)]

# trees는 1차원 배열이 
for _ in range(M):
    y, x, size = map(int,input().split())
    section_idx = N*(y-1) + (x-1) # 1차원 리스트에 해당하는 idx로 변경
    trees[section_idx].append(size)

# 가을일 때, 움직이는 방향 모음
adj = [
(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1) 
]


while K:
    
    for i in range(N):
        for j in range(N):
            section_idx = N*i + j
            trees_len = len(trees[section_idx])
            if  trees_len >= 1:
                trees[section_idx].sort()

                idx = 0
                rm_start_idx = -1
                rm_flag = False
                
                # 봄인 경우
                while idx < trees_len:
                    if rm_flag is False:
                        if nut[i][j] < trees[section_idx][idx]:
                            rm_flag = True
                            rm_start_idx = idx
                        else:
                            nut[i][j] -= trees[section_idx][idx]
                            trees[section_idx][idx] += 1
                    
                    # 여름인 경우 죽은 나무들 처리
                    if rm_flag is True:
                        nut[i][j] += (trees[section_idx][idx] // 2)

                    idx+=1
                
                # 죽은 나무들 제거하고 땅에 나무들 다시 설정
                if rm_flag is True:
                    trees[section_idx] = trees[section_idx][0 : rm_start_idx]
                
              
    for i in range(N):
        for j in range(N):
            section_idx = N*i + j
            # 가을의 경우 5의 배수에 해당하는 나무들 처리
            for age in trees[section_idx]:
                if age % 5 == 0:
                    for dy, dx in adj:
                        ny = i+dy 
                        nx = j+dx
                        if 0<=ny<N and 0<=nx<N:
                            create_trees_idx = N*ny + nx
                            trees[create_trees_idx].append(1)

            # 겨울의 경우 양분 보충
            nut[i][j] += A[i][j]

    K-=1



answer = 0
for section in trees:
    answer += len(section)

print(answer)