[BOJ] 16235. 나무 재테크

문제

나무 재테크 (https://www.acmicpc.net/problem/16235)

풀이

1. 초기 접근

• 문제조건 해석
  • 역시 삼성 문제는 뭔가 글이 많다.
    • 세세하게 잘 읽어야한다.
    • 두번 세번 읽어줘야 한다. 문제를 잘 읽고 코딩하자.
  • 삼성 문제의 대표적인 시뮬레이션 문제다.
    • 문제에서 주어진 대로 그냥 짜기만 하면 된다.
    • 핵심은, 과연 올바른 자료구조로 잘 구현할 수 있는가? 다.
• 알고리즘
  • 정말 문제에 나온대로 하나씩 코딩하면 된다.
  • 핵심은, 나이가 어린 나무들부터 양분을 섭취해야하는데, 이를 위해 deque 를 썼다.
  • 자세한 건 코드 주석 참조.
• 코드

from collections import deque

dxs = [-1, -1, 0, 1, 1, 1, 0, -1]
dys = [0, 1, 1, 1, 0, -1, -1, -1]

# n, m, k 입력
n, m, k = list(map(int, input().split()))

"""
nut : 매년 뿌릴 양분을 담는 2차원 리스트다. 문제에서는 A[i][j] 라고 표기되어있음.
board : board[x][y]는 x, y에 현재 양분이 얼마나 있는지를 담는다.
trees_dict: trees_dict[(x, y)]는 x, y에 있는 현재 나이의 나무들을 담는다.
            deque로 이루어져있어, x, y에 새로 태어나는 나무들은 큐 앞쪽부터 채워진다.
added_nut : added_nut[x][y] 는 x, y 좌표에 죽은 나무들이 남길 양분 값을 담는다.
"""
nut = [list(map(int, input().split())) for _ in range(n)]
board = [[5]*n for _ in range(n)]
trees_dict = {(i,j): deque() for i in range(n) for j in range(n)}

# 초기 나무들의 값을 입력받는다.
for _ in range(m):
    x, y, age = list(map(int, input().split()))
    trees_dict[(x-1, y-1)].append(age)

year = 0
while True:
    added_nut = [[0]*n for _ in range(n)]

    # 봄
    for (x, y), trees in trees_dict.items():
        surived_trees = deque()

        # 나이가 어린 나무부터 양분을 먹는다. (deque)
        for tree in trees:
            if board[x][y] >= tree:
                # 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.
                surived_trees.append(tree + 1)
                board[x][y] -= tree
            else:
                # 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
                added_nut[x][y] += tree // 2

        # 살아남은 나무들로 갱신한다.
        trees_dict[(x, y)] = surived_trees

    # 여름
    # 여름에는 봄에 죽은 나무가 양분으로 변하게 된다.
    for (x, y), trees in trees_dict.items():
        board[x][y] += added_nut[x][y]

    # 가을
    new_trees = {(i,j): 0 for i in range(n) for j in range(n)}
    for (x, y), trees in trees_dict.items():
        for tree in trees:
            # 번식하는 나무는 나이가 5의 배수이어야 하며
            if tree % 5 == 0:
                # 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 
                for dx, dy in zip(dxs, dys):
                    nx, ny = x + dx, y + dy
                    if nx >= 0 and nx < n and ny >= 0 and ny < n:
                        new_trees[(nx, ny)] += 1
    for (x, y), size in new_trees.items():
        for _ in range(size):
            trees_dict[(x, y)].appendleft(1)

    # 겨울
    # 겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 
    for i in range(n):
        for j in range(n):
            board[i][j] += nut[i][j]

    year += 1

    # K년 후, 
    if year == k:
        answer = 0
        for (x, y), trees in trees_dict.items():
            answer += len(trees)
        print(answer)
        break

여담

작년 하반기 삼성 테스트 문제로 보이는데, 당시에 C++ 로 짰는데 시간초과가 떴던 기억이 난다.
근데 파이썬으로 푸니, 자료구조도 훨씬 수월하고… dict 와 deque 의 위엄을 느낄 수 있는 문제