[백준 16235]나무 재테크

[백준 16235]나무 재테크

문제 링크

#include "header.h"
using namespace std;
int n, m, k, ans;
int nutrition[12][12];
int forest[12][12];
typedef struct
{
    int x; //위치
    int y;
    int z; //나이
} Tree;
deque<Tree> tree[12][12];
void input()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> forest[i][j];
            nutrition[i][j] = 5;
        }
    }

    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        tree[x][y].push_back({x, y, z});
    }
}
vector <Tree> spring()
{
    vector <Tree> dead;
    // 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.
    // 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다.
    // 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
    // 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (tree[i][j].size() > 0)
            {
                int size = tree[i][j].size();
                for (int k = 0; k < size; k++)
                {
                    Tree t = tree[i][j].front();
                    tree[i][j].pop_front();
                    
                    if(t.z <= nutrition[i][j]){
                        int age = t.z;
                        nutrition[i][j] -= age;
                        tree[i][j].push_back({i, j, age+1});
                    }else if(t.z > nutrition[i][j]){
                        dead.push_back(t);
                    }
                }
            }
        }
    }
    return dead;
}
void fall(){
    //가을에는 나무가 번식한다.
    //번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
    //어떤 칸 (r, c)와 인접한 칸은 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), 
    //(r+1, c), (r+1, c+1) 이다.
    //상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.
    int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (tree[i][j].size() > 0)
            {
                for(int k=0; k<tree[i][j].size(); k++){
                    if(tree[i][j][k].z % 5 == 0){
                        for(int a=0; a<8; a++){
                            int nx = i + dx[a];
                            int ny = j + dy[a];

                            if(nx > n || ny > n || nx <= 0 || ny <= 0) continue;
                            
                            //새로운 나무
                            tree[nx][ny].push_front({nx, ny, 1});
                        }
                    }
                }
            }
        }
    }

}
int winter(){
    //겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다.
    //각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.
    int cnt=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(tree[i][j].size() > 0){
                cnt += tree[i][j].size();
            }
            nutrition[i][j] += forest[i][j];
        }
    }

    return cnt;

}
void summer(vector <Tree>& dead){
    for(int i=0; i<dead.size(); i++){
        int age = dead[i].z / 2;
        int x = dead[i].x;
        int y = dead[i].y;

        nutrition[x][y] += age;
    }
}
void solve()
{
    for(int i=0; i<k; i++)
    {
        vector <Tree> dead = spring();
        summer(dead);
        fall();
        ans = winter();
    }
    
    cout << ans << endl;
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    input();
    solve();
    return 0;
}

• deque가 아닌 vector로 tree를 만들고, 봄이 올때마다 sorting을 해주니 시간초과가 났다.
• 새로운 나무가 심어지면 1로 심어져서, 가장 작은 나이이기 때문에 deque에 push_front()를 해준다.
• spring에서 deque의 사이즈만큼 돌면서 죽은 나무는 vector에 넣어주고, 살아있는 나무는 push_back으로 계속 살려준다.