[BOJ] 16235번 나무 재테크 (Python) [삼성 SW 역량 테스트 기출 문제]

문제

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

풀이

문제를 읽고 문제에서 하라는대로 하면 되는 구현 문제임은 금방 알 수 있었다.
다만, 이때 나무를 어떤 자료구조로 담아서 저장할지가 문제였다.
같은 좌표에 대해 나이가 가장 어린 나무부터 차례대로 찾는걸 어떻게 효율적으로 할지 고민했다.

그런데 항상 새로 추가되는 나무의 나이가 1이므로 최근에 추가된 나무일수록 나이가 어리다는 사실을 깨닫고 새로운 나무는 리스트에 append하고, 양분흡수할때 list의 뒷부분부터 탐색하도록 했다.
즉, 다음과 같은 자료구조로 저장

{(x,y):[5,4,1,1]}

딕셔너리를 items()로 for문을 돌며 중간에 딕셔너리의 데이터를 바꾸면 에러가 발생하여 따로 바꿀 정보를 담아둔 뒤 따로 처리하는 방식으로 해결했는데 더 나은 방법이 있을지 모르겠다.

Python3로는 통과못하고 PyPy3로 통과하였다.

손으로 수도코드 작성하는 과정을 조금 더 했어야 했다. 너무 바로 코드 작성으로 들어가서 만약 꼬였으면 삽질 오래 했을 수도 있겠다고 생각했다.

# 2022/10/05 00:05시작 01:00 AC 처리
# 문제: https://www.acmicpc.net/problem/16235


if __name__ == "__main__":
    from collections import defaultdict

    def is_valid(x,y):
        if 0<=x<N and 0<=y<N:
            return True
        return False
    
    dx = [-1,-1,-1,0,0,1,1,1]
    dy = [-1,0,1,-1,1,-1,0,1]

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

    # A는 겨울마다 추가되는 양분의 양
    A = [list(map(int, input().split())) for _ in range(N)]
    
    # 초기 양분은 모두 5
    nutrient = [[5]*N for _ in range(N)]

    tree_info = defaultdict(list)
    for _ in range(M):
        x,y,z = map(int, input().split())
        x,y = x-1, y-1 # 인덱스에 맞게 변경
        tree_info[(x,y)] = [z] # 모두 다른 좌표로 처음에 주어진다
        # append 되는 값이 항상 어리다(항상 내림차순)

    for _ in range(K):
        die_tree_info = []
        # 봄
        for (x,y), age_list in tree_info.items():
            for i in reversed(range(len(age_list))): # 나이적은 순서대로
                if age_list[i] <= nutrient[x][y]:
                    nutrient[x][y] -= age_list[i] # 나이만큼 양분먹고
                    age_list[i] += 1 # 나이 1증가
                else:
                    die_tree_info.append((x,y,i,age_list))
                    break
        #print("봄 적용 후: ", tree_info)

        # 여름
        for x,y,i,age_list in die_tree_info:
            tree_info[(x,y)] = age_list[i+1:] # 죽는 나무 제외하고
            for age in age_list[:i+1]:
                nutrient[x][y] += age//2
        #print("여름 적용 후: ", tree_info)

        # 가을
        add_tree_info = []
        for (x,y), age_list in tree_info.items():
            for age in age_list:
                if age%5==0: # 번식
                    for i in range(8):
                        new_x = x + dx[i]
                        new_y = y + dy[i]
                        if is_valid(new_x, new_y):
                            add_tree_info.append((new_x,new_y))
        for x, y in add_tree_info:
            tree_info[(x,y)].append(1)
        #print("가을 적용 후: ", tree_info)

        # 겨울
        for i in range(N):
            for j in range(N):
                nutrient[i][j] += A[i][j]
    
    print(sum(len(x) for x in tree_info.values()))