BOJ - 나무 재테크 16235번 (python)

❓ 문제 - 백준 나무 재테크 16235번 - python 풀이법

출처 

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

16235번: 나무 재테크

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 땅의 양분 정보를 저장할 food, 나무의 나이를 저장할 tree, 겨울철에 땅의 양분을 줄 feed 리스트를 사용한다.
• n의 범위가 1 ~ 10 사이 이므로 리스트로 선언하여 이중 for문을 통에 접근해도 시간 복잡도에 걸리지 않을 수 있다.
• grow() 함수를 통해 봄과 여름에 대해 처리는 이중 for문으로 리스트 접근할 때 한번에 처리하고 가을과 겨울의 처리는 따로하여 1년을 지나게 한다. k년의 나무 재테크동안 grow() 함수를 k번 호출한 후 tree리스트에 몇 개의 나무가 심어져 있는지 세어서 정답을 출력한다.
• 봄과 여름에는 나무를 키우고 제거하기 위해서 일단 한 땅에 여러 나무가 심어질 수 있고 양분을 먹어 성장하는 순서는 어린나무부터 하므로 i행 j열에 있는 나무 나이를 정렬하기 위해  tree[i][j] 를  sort해준다. i행 j열에 심어져 있는 나무가 있다면 temp_tree 리스트를 통해 양분을 먹고 나이가 증가한 나무의 나이를 넣어주고, 해당 땅의 양분보다 나이가 많은 나이는 죽은 나무이므로 죽은 나무의 나이를 dead_tree를 통해 저장한다. 또한 봄의 처리 후 여름으로 죽은 나무들의 나이를 합한 것을 2로 나누어 해당 땅에 양분으로 더해주면서 여름을 처리한다.
• 가을이 오면 모든 땅의 행과 열을 살펴, 해당 땅의 나무가 만약 5로 나누어진다면  dx, dy를 활용해 8방향으로 나무가 번식될 수 있어서 해당 nx, ny가 인덱스 범위에 들어가면 해당 탐색된 지역에 나이가 1살인 나무를 추가해준다.
• 겨울이 되면 땅의 양분을 추가하기 위해 입력받은 추가되는 양분의 양을 현재 땅의 양분의 양에 더해준다.

2. 문제 풀면서 생겼던 이슈들

• 처음 봄,여름,가을,겨울을 따로 처리하기로 구현했고, 봄에서 죽은 나무들의 정보를 queue에 입력받아 여름이 오면 죽은 나무들을 양분으로 바꾸도록 하였더니 시간초과가 발생했다. -> 이중 for문 안에서 같이 처리될 수 있으면 시간 절약을 위해 같이 구현해야겠다.
• 중간 중간 입출력 예시들을 print문으로 처리해서 구현의 오류를 해결해보자.

 

 

 

💻 소스코드

n, m, k = map(int, input().split())
tree = [[[] for _ in range(n)] for _ in range(n)]

feed = [list(map(int, input().split())) for _ in range(n)]
for _ in range(m):
    x, y, z = map(int, input().split())
    tree[x-1][y-1].append(z)

food = [[5] * n for _ in range(n)]
dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, 1, -1, -1, 1]


def grow(food, tree):
    for i in range(n):
        for j in range(n):
            if tree[i][j]:
                tree[i][j].sort()
                temp_tree, dead_tree =[], 0
                for t in tree[i][j]:
                    if food[i][j] >= t:
                        food[i][j] -= t
                        t += 1
                        temp_tree.append(t)
                    else:
                        dead_tree += t // 2
                food[i][j] += dead_tree
                tree[i][j] = []
                tree[i][j].extend(temp_tree)

    for i in range(n):
        for j in range(n):
            if len(tree[i][j]) == 0:
                continue
            for p in range(len(tree[i][j])):
                if (tree[i][j][p] % 5 == 0):
                    x, y = i, j
                    for q in range(8):
                        nx = x + dx[q]
                        ny = y + dy[q]
                        if 0 <= nx < n and 0 <= ny < n:
                            tree[nx][ny].append(1)

    for i in range(n):
        for j in range(n):
            food[i][j] += feed[i][j]


for _ in range(k):
    grow(food, tree)

answer = 0
for i in range(n):
    for j in range(n):
        answer += len(tree[i][j])

print(answer)