[백준 16235] 나무 재테크

🍎[백준 16235] 나무 재테크

문제링크

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

16235번: 나무 재테크

 

⚾ 코드

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
nutrients = [[5]*n for _ in range(n)] # 양분 저장
trees = [[[] for _ in range(n)] for _ in range(n)] # 나무들 저장

for _ in range(m):
    x, y, age = map(int, input().split())
    trees[x-1][y-1].append(age)

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

# k년이 지난 후 살아남은 나무 구하기


def check_range(x, y): # 범위 확인
    if x >= 0 and y >= 0 and x < n and y < n:
        return True
    return False


def spring_and_summer():
    # spring
    die = [] # 죽은 나무 리스트
    for i in range(n):
        for j in range(n):
            finish = [] # 산 나무들
            tree_sort = sorted(trees[i][j])
            for age in tree_sort:
                if nutrients[i][j] >= age:
                    nutrients[i][j] -= age
                    finish.append(age+1)
                else:
                    die.append((i, j, age))
            trees[i][j] = finish[:]

    # summer
    for x, y, age in die:
        nutrients[x][y] += age//2 # 죽은 나무들의 양분 더하기


def autumn():
    for i in range(n):
        for j in range(n):
            for age in trees[i][j]:
                if age % 5 == 0: # 5로 나누어 떨어질 경우, 주변 8곳에 나이1인 나무 추가
                    for a in range(8):
                        nx = i+dx[a]
                        ny = j+dy[a]

                        if check_range(nx, ny):
                            trees[nx][ny].append(1)


def winter():
    # 양분 추가
    for i in range(n):
        for j in range(n):
            nutrients[i][j] += arr[i][j]


def calculate(): # 마지막 결과 계산
    res = 0
    for i in range(n):
        for j in range(n):
            res += len(trees[i][j])
    return res


for _ in range(k):
    # 봄, 여름, 가을, 겨울 k번 반복
    spring_and_summer() # 봄, 여름
    autumn() # 가을
    winter() # 겨울

print(calculate())

 

🔔 해결 과정 & 깨달은 점

- simulation 카테고리에 있던 문제였던 만큼, 문제는 크게 어렵지 않았지만 구현하는 데에 까다로웠다.

 

- 처음에 접근은 defaultdict를 써서 key에는 (x,y) 값을, value에는 나무들의 나이 값을 넣어서 해보려고 했다.

그러나 딕셔너리를 for문으로 돌면서 작업을 할 때  dictionary changed size during iteration 오류가 나는 것이다. 다른 방법을 찾아야 했다.

 

그래서 방법을 바꾸어 진행했다. 리스트의 (x,y)좌표의 리스트에 나무들을 저장하며 풀었다.

테스트케이스도 다 맞았지만 제출하자마자 틀렸습니다가 떴다.

 

코드를 자세히 살펴보니 간과한 부분이 있었다.

 

나무가 양분을 먹을 때 나이가 적은 순으로 먹기 때문에 sort를 해서 문제를 풀었다.

그래서 양분보다 나무의 나이가 많을 때 die 리스트에 넣고 바로 break를 했다. 그 뒤의 나무들은 당연히 나이가 더 많이 때문에 딱히 볼필요도 없을 것이라고 생각했던 것이다.

def spring_and_summer():
    # spring
    die = []  # 죽은 나무 리스트
    for i in range(n):
        for j in range(n):
            finish = []  # 산 나무들
            tree_sort = sorted(trees[i][j])
            for age in tree_sort:
                if nutrients[i][j] >= age:
                    nutrients[i][j] -= age
                    finish.append(age+1)
                else:
                    die.append((i, j, age))
                    break
            if finish:
                trees[i][j] = finish[:]

    # summer
    for x, y, age in die:
        nutrients[x][y] += age//2  # 죽은 나무들의 양분 더하기

 

그러나 이렇게 하면, 뒤의 나이 많은 나무들이 die 리스트에 들어가지 못하게 된다.

 

그래서 그 부분을 고쳐주었더니 해결되었다.