[pypy] 백준 16235 - 나무 재테크

출처 : 백준, https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

 

 

# 같은 곳에 여러 개의 나무가 심어질 수 있다.
# 모든 나무는 나이를 한 살 씩만 먹는다.
# 새로 추가되는 모든 나무의 나이는 1살이다.

# NxN의 격자에 M개의 나무를 심어서 K년 동안 키울 것
# 나무 좌표의 r, c는 1부터 시작
# 모든 칸은 처음에 양분이 5만큼 들어있음

# 봄
# 나무는 땅에서 나이만큼의 양분을 먹고 나이 + 1
# 하나의 칸에 여러 개의 나무가 있다면 어린 나무부터 먹음
# 양분을 못 먹은 나무는 즉시 죽음

# 여름
# 죽은 나무들의 나이 // 2만큼 땅에 양분 추가

# 가을
# 나무의 나이가 5의 배수라면 주위 8칸에 나이가 1인 나무 생성

# 겨울
# 로봇이 돌아다니며 땅에 양분 추가

 

 

먼저, 생각해야 할 부분

 

1. 삼성 기출 문제다.

    삼성 기출 문제의 특징은 시간 초과를 피하기 위해서 최적화 시킬 수 있는 부분을 어떻게든 찾아서 무조건 최적화 시켜야한다.

    최적화 해야하는 것들 중 대표적인 몇 가지는

 

    - 입력을 받으면서 처리할 수 있는 것을 바로 처리하기

    - 루프를 많이 돌지 말기, 돌아야 할 경우 같이 처리할 수 있는 로직 묶어서 처리하기

 

   를 예로 들 수 있다.

 

 2. 파이썬 위한 마법의 코드

 

import sys

input = sys.stdin.readline().strip()

 

---

 

풀이

 

from collections import deque
import sys

def input():
    return sys.stdin.readline().strip()

class Tree:
    def __init__(self, r, c, age):
        self.coordinate = (r, c)
        self.age = age

    def __lt__(self, other):
        if self.age <= other.age:
            return True
        else:
            return False

class GroundInfo:
    def __init__(self, r, c):
        self.coordinate = (r, c)
        self.food = 5
        self.alive_tree_list = deque()
        self.dead_tree_list = deque()

    def plantTree(self, tree):
        self.alive_tree_list.appendleft(tree)

    def growTree(self):
        origin_alive_tree_list = self.alive_tree_list
        new_alive_tree_list = deque()
        
        while len(origin_alive_tree_list) > 0:
            tree = origin_alive_tree_list.popleft()
            
            if tree.age <= self.food:
                self.food -= tree.age
                tree.age += 1
                new_alive_tree_list.append(tree)
            else:
                origin_alive_tree_list.appendleft(tree)
                break

        self.dead_tree_list = origin_alive_tree_list
        self.alive_tree_list = new_alive_tree_list

        return (len(self.alive_tree_list), len(self.dead_tree_list))

    def clearDeadTree(self):
        while len(self.dead_tree_list) > 0:
            tree_object = self.dead_tree_list.pop()
            self.food += (tree_object.age // 2)

def Autumn(ground, alive_tree_tile_set):
    # 살아있는 나무들 중 수명이 5인 아이들을 대상으로 주위에 나이가 1인 나무 추가

    n = len(ground)
    diff = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

    for r, c in alive_tree_tile_set:
        ground_info = ground[r][c]

        for tree in ground_info.alive_tree_list:
            if tree.age % 5 == 0:
                # 주위 8칸에 새 나무 심기
                for dr, dc in diff:
                    nr = r + dr
                    nc = c + dc

                    if 0 <= nr < n and 0 <= nc < n:
                        ground[nr][nc].plantTree(Tree(nr, nc, 1))

    return

def SpringSummgerWinter(ground, food_map):
    # 다른 타일에 영향을 미치지 않는 작업들은 한 번에
    n = len(ground)

    alive_tree_tile_set = set()

    for r in range(n):
        for c in range(n):
            if len(ground[r][c].alive_tree_list) > 0:
                #Spring
                alive_tree_count, dead_tree_count = ground[r][c].growTree()

                if alive_tree_count > 0:
                    alive_tree_tile_set.add((r, c))

                # Summer
                if dead_tree_count > 0:
                    ground[r][c].clearDeadTree()

            # Winter
            ground[r][c].food += food_map[r][c]

    return alive_tree_tile_set

def calcAliveTree(ground):
    count = 0

    for r in range(len(ground)):
        for c in range(len(ground)):
            count += len(ground[r][c].alive_tree_list)

    return count

def solution(n, m, k, food_map, tree_info):
    ground = [[GroundInfo(r, c) for c in range(n)] for r in range(n)]

    # 땅에 나무 심기
    for r, c, age in tree_info:
        # 땅에 나무를 심는다.
        r -= 1
        c -= 1

        ground[r][c].plantTree(Tree(r, c, age))

    for _ in range(k):
        alive_tree_tile_set = SpringSummgerWinter(ground, food_map)
        Autumn(ground, alive_tree_tile_set)

    return calcAliveTree(ground)

n, m, k = map(int, input().split())
food_map = [list(map(int, input().split())) for _ in range(n)]
tree_info = sorted([list(map(int, input().split())) for _ in range(m)], reverse = True)

print(solution(n, m, k, food_map, tree_info))

 

이 풀이는 Python3로는 시간 초과가 나왔고, Pypy3로 통과했다.

tree_info를 받자마자 내림차순으로 정렬해서 appendleft 시 가장 어린 나무가 deque에 맨 앞에 오도록 만들었다.

처음에는 우선순위 큐를 사용했는데, 새로 추가되는 나무는 1살로 가장 어리기 때문에 가장 앞에 추가되면 되서

처음에만 나이순으로 alive_tree_list를 잘 정렬해둔다면, 굳이 이후에 정렬할 필요가 없다.

 

---

시간 복잡도

-

 

알게 된 점

 

heapq를 통한 우선순위 큐의 우선순위를 커스텀 하는 방법

 

1. 배열로 넣기

    [우선순위, 요소]로 넣으면, 우선순위를 보고 배열에 넣는다.

 

2. def __lt__(self, other) 재정의하기

    heapq는 < 연산자를 통해 정렬되기 때문에, __lt__ 함수를 재정의하여 우선순위를 비교가 적용되도록 만들 수 있다.

    이는 따로 클래스를 선언해 객체를 만들 때 유용하다.

 

문제에서 우선순위 큐를 사용하려할 때 주의할 점
내부 요소를 빼지 않고 우선 순위를 바꿀 경우 알아서 재배열되지 않는다.
우선순위 큐를 유지하기 위해서는 무조건 빼고 다시 넣는 과정이 필요하다.

 

테스트하기 쉬운 코드

배열을 순회하면서 작업을 수행해야할 경우
한 요소에 대하여 작동하는 함수를 만들어 놓으면 테스트하기가 쉽다.
이 함수를 배열을 순회하면서 동작시키도록 만들면 된다

 

기타

다른 작업들과 병렬적으로 처리할 수 있는 작업은 루프를 돌 때 한 번에 처리하면 좋다.

정렬은 비싼 기능이다. 정렬을 사용할 경우 이를 최소하하려고 노력해야한다. 정말로 정렬이 필요한 경우인지 생각해보자.

 

고찰

 

삼성 문제는 풀 때마다, 내가 너무 어렵게 접근하는 것 같다.

 

Github

백준 16235 - 나무 재테크

 

Reference

파이썬 heapq 커스텀 정렬 이용하기