[Python] 백준 16235 나무 재테크

1. 문제 링크

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

16235번: 나무 재테크

---

2. 문제 요약

4계절에 맞게 구현을 하여 k 년이 지난 후 살아있는 나무 개수를 출력한다.

---

3. 아이디어 정리

1. 나무 나이를 저장할 그래프를 새로 생성한다. - 3차원으로 저장
2. k 년 동안 4계절을 반복 진행한다.
   1. 봄: 자신의 나이만큼 양분 먹고 나이 + 1 한 칸에 여러 개 나무가 있다면 어린나무부터
   2. 여름: 죽은 나무 = (나이 // 2)로 현재 양분에 넣어준다.
   3. 가을: 나무 번식 - 나이가 5 배수이어야하고, 인접한 8개 칸에 나이가 1 나무 생긴다.
   4. 겨울: 로봇이 양분을 추가한다.
3. 나무의 수를 세어준다.

---

4. 문제 풀이

4-1. 내 풀이

"""
 return: k년이 지난 후 나무의 개수
"""
import sys

dx = [1, -1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, 1, -1, -1]

n, m, k = map(int, sys.stdin.readline().split())  # n*n 땅, m개의 나무, k년

a = list()                                          # 겨울에 추가될 양분
now_a = [[5] * n for _ in range(n)]                 # 현재 양분은 5로 세팅
tree = [[[] for _ in range(n)] for _ in range(n)]   # 나무 관련 - 3차원으로 표현(같은 자리에 나무가 여러개 있어서)

# 추가될 양분 관련 입력
for _ in range(n):
    a.append(list(map(int, sys.stdin.readline().split())))

# 나무 나이 관련 입력
for _ in range(m):
    x, y, z = map(int, sys.stdin.readline().split())   # (x, y) 나무 위치, 나무 나이
    tree[x - 1][y - 1].append(z)

# k년 동안 4계절 반복하기
for _ in range(k):
    # 1. 봄: 자신의 나이만큼 양분 먹고 나이 + 1 한칸에 여러개 나무가 있다면 어린나무부터
    for i in range(n):
        for j in range(n):
            if not tree[i][j]:  # 해당 자리에 나무가 없으면 다음 탐색
                continue
            tree[i][j].sort()   # 어린나무부터 먹기 위함
            # 해당 부분 모두 처음부터 돌면 시간 초과 - 다른 블로그 참고(배열 인덱싱 활용) 
            idx = 0
            while idx < len(tree[i][j]):
                if tree[i][j][idx] <= now_a[i][j]:
                    now_a[i][j] -= tree[i][j][idx]
                    tree[i][j][idx] += 1
                    idx += 1
                else:
                    die = tree[i][j][idx:]
                    # 2. 여름: 죽은 나무 = (나이 // 2)
                    for now in die:  
                        now_a[i][j] += (now // 2)
                    tree[i][j] = tree[i][j][:idx]
                    break
    # 3. 가을: 나무 번식 - 나이가 5 배수이어야하고, 인접한 8개 칸에 나이가 1 나무 생김
    for i in range(n):
        for j in range(n):
            for age in tree[i][j]:
                if age % 5 == 0:  # 5의 배수인 경우, 인접한 8개의 칸에 나이 1 나무 추가
                    for d in range(8):
                        nx = dx[d] + i
                        ny = dy[d] + j
                        if nx < 0 or ny < 0 or nx >= n or ny >= n:
                            continue
                        tree[nx][ny].append(1)
    # 4. 겨울: 로봇이 양분을 추가한다.
    for i in range(n):
        for j in range(n):
            now_a[i][j] += a[i][j]

# 나무의 수 세기
result = 0
for i in range(n):
    for j in range(n):
        if tree[i][j]:
            result += len(tree[i][j])

print(result)

 

---

5. 결론

• 구현 문제
• 나무 나이 저장을 3차원으로 해야한다는 점을 파악해야 한다.
• 봄~여름 부분 구현이 어려웠던 문제이다. (시간 초과 문제)