BOJ 16235 · 나무 재테크

알고리즘 분류 : 시뮬레이션  

봄, 여름, 가을, 겨울에 따라 나무가 개수가 변할 때, K년이 지난 후 남아있는 나무의 개수를 구하는 문제다. 문제 자체가 복잡하기 때문에 제대로 정독하고 계절 순서대로 구현하는 것이 좋다.

• 봄에는 나무가 자신의 나이만큼 땅에 있는 양분을 먹고, 나이가 1 증가한다. 한 구역의 땅에 나무가 여러 그루 존재할 수 있다. 
• 나이가 어린 나무부터 양분을 먹는다. 땅에 남아있는 양분이 부족하여 양분을 먹지 못한 나무는 죽는다.
• 나이 순서대로 먹는다는 내용 때문에, 단순히 나이를 오름차순 정렬하면 비효율적이다.
• 효율적인 방법은 '덱' 자료구조를 사용하는 것이다. 나무를 새로 심을 때는 Front push하고, 나무가 죽을 때는 Back pop을 해주는 것이다. 또는 '힙' 자료구조를 사용하면 된다.
• 여름에는 죽은 나무가 양분으로 변하여 땅에 추가된다. 양분은 나무가 죽기 직전 나이의 1/2만큼 추가된다.
• 여름에 진행되는 과정은 봄과 연계해서 할 수 있기 때문에, 양분을 먹는 과정이 끝난 후 바로 이어서 하면 된다.
• 가을에는 나무를 심는다. 나무의 나이가 5의 배수일 때, 인접한 8곳에 새로 나무를 심는다. 새로 나무를 심을 때 앞서 말한 것처럼 덱의 앞에 추가한다.
• 겨울에는 입력으로 받은 양분이 추가된다. 가을과 연계해서 집어넣으면 된다.

---

C++ 소스코드

#include <cstdio>
#include <deque>
using namespace std;

int N, M, K, ans;
int a[10][10];
int nutrient[10][10];
deque<int> tree[10][10];
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

void spring_summer() {
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            int &nt = nutrient[i][j];
            deque<int> &tr = tree[i][j];
            for (int k=0; k<(int)tr.size(); k++) {
                if (nt >= tr[k]) { // Spring
                    nt -= tr[k];
                    tr[k]++;
                } else { // Summer
                    while (k < (int)tr.size()) {
                        nt += (tr.back()/2);
                        tr.pop_back();
                        ans--;
                    }
                    break;
                }
            }
        }
    }
}

void fall_winter() {
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            for (int k=0; k<(int)tree[i][j].size(); k++) {
                if (tree[i][j][k]%5 == 0) { // Fall
                    for (int t=0; t<8; t++) {
                        int x = i+dx[t], y = j+dy[t];
                        if (x < 0 || x >= N || y < 0 || y >= N) continue;
                        tree[x][y].push_front(1);
                        ans++;
                    }
                }
            }
            nutrient[i][j] += a[i][j]; // Winter
        }
    }
}

void solve() {
    while (K--) {
        spring_summer();
        fall_winter();
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d %d %d", &N, &M, &K);
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            scanf("%d", &a[i][j]);
            nutrient[i][j] = 5;
        }
    }
    for (int i=0; i<M; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        tree[x-1][y-1].push_back(z);
        ans++;
    }
    solve();
    return 0;
}

---

PyPy3 소스코드

from sys import stdin
from collections import deque
input = stdin.readline

ans = 0
dx, dy = (-1, -1, -1, 0, 0, 1, 1, 1), (-1, 0, 1, -1, 1, -1, 0, 1)
N, M, K = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
tree = [[deque() for _ in range(N)] for _ in range(N)]
nutrient = [[5 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    x, y, z = map(int, input().split())
    tree[x-1][y-1].append(z)
    ans += 1

def spring_summer():
    global ans
    for i in range(N):
        for j in range(N):
            for k in range(len(tree[i][j])):
                if nutrient[i][j] >= tree[i][j][k]:
                    nutrient[i][j] -= tree[i][j][k]
                    tree[i][j][k] += 1
                else:
                    while k < len(tree[i][j]):
                        nutrient[i][j] += (tree[i][j].pop()//2)
                        ans -= 1
                    break

def fall_winter():
    global ans
    for i in range(N):
        for j in range(N):
            for k in range(len(tree[i][j])):
                if tree[i][j][k]%5 == 0:
                    for t in range(8):
                        x, y = i+dx[t], j+dy[t]
                        if x < 0 or x >= N or y < 0 or y >= N:
                            continue
                        tree[x][y].appendleft(1)
                        ans += 1
            nutrient[i][j] += a[i][j]

def solve():
    for _ in range(K):
        spring_summer()
        fall_winter()
    print(ans)

solve()

✓ C++과 같은 방법으로 알고리즘을 구현했지만, Python 3로 제출하면 시간 초과가 나온다.

✓ 개선이 필요한 알고리즘이다. 같은 코드를 PyPy3로 제출하면 성공한다.

---

참고

• 백준 온라인 저지 : BOJ 16235