keiprodev
BaekJoon

Baekjoon. 16235. 나무 재테크

keipro
2026-02-23
3 Mins Read
108 Views
0 Comments

16235. 나무 재테크

[문제 사이트 바로가기]

문제 설명 요약

  • N * N 크기의 땅에 나무들이 존재한다.

  • 나무들은 사계절을 보내며, 각 사계절마다 다음과 같은 과정을 반복하게 된다.

    • 봄 : 자신의 나이만큼 땅에 존재하는 양분을 먹으며, 나이가 1 증가한다. 만약, 나이만큼 양분을 먹을 수 없으면 죽으며, 여러 나무가 존재한다면 나이가 가장 어린 나무가 먼저 양분을 먹게 된다.
    • 여름 : 봄에 죽은 나무가 양분으로 변하게 된다. 죽은 나무의 나이를 2로 나눈 값이 나무에 있던 땅에 양분으로 추가된다.
    • 가을 : 번식하는 단계를 거치게 된다. 번식하는 나무는 나이가 5의 배수여야 하고, 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
    • 겨울 : 땅에 양분을 추가한다. 각 땅마다 얼마만큼 추가되는지는 입력값으로 주어진다.

  • K 년이 지난 후 살아남은 나무들의 개수를 출력하기.



문제 풀이

  • 문제 풀이에 나오는 내용 그대로 진행하면 되기 때문에 특별히 문제 풀이에 대한 내용을 말할 부분은 없어보임. 주석에 각 계절별로 처리를 해주고 있기 때문에 이 부분을 확인해보면 될 것 같다. 문제 풀이에 대한 내용 보다는 어떠한 자료구조들을 활용했고, 왜 쓰게 되었는지 등등을 소개하는 것이 더 좋을 것이라 판단하여 이 내용 위주로 진행하게 되었다.
1. 구조체 활용

  • 땅에 대한 개념, 나무에 대한 개념, 등등… 문제에 주어진 내용들이 여러가지가 많이 있기 때문에 구조체로 자료들을 관리하는 방식으로 처리하게 되었다.

  • 크게 사용한 구조체는 총 3개이다.

  1. Tree : 좌표 정보와 나이를 담을 수 있는 구조체.
struct Tree
{
    Tree(int y, int x, int age)
        :y(y), x(x), age(age)
    {

    }

    int y;
    int x;
    int age;
};
  1. Cell : 땅에 대해서, 중복으로 존재하는 나무들을 담을 데이터, 양분의 양.
struct Cell
{
    Cell() : nutrient(5)
    {

    }

    priority_queue<Tree, vector<Tree>, pqCompare> trees;
    int nutrient;
};
  1. pqCompare : 위의 우선순위 큐의 비교 연산을 수행할 수 있도록 해주는 비교용 구조체.
struct pqCompare
{
    bool operator()(const Tree& tree1, const Tree& tree2) const
    {
        return tree1.age > tree2.age;
    }
};
2. 우선순위 큐 사용 이유?
  • 땅에 중복으로 나무가 존재할 수 있으며, 특히 봄 계절에 나이가 어린 나무가 먼저 양분을 먹는다는 규칙이 들어가게 되어 우선순위 큐의 min-heap을 사용하게 되었다.
3. 나무들이 존재하는 포지션
  • Grid 전체 순회하며 나무들이 존재할 때 순회하는 방식도 물론 괜찮은 방법이지만, 나무들이 존재하는 좌표에 대해서만 순회를 해주는 것도 좋을 것 같아서 이를 위해 set자료구조를 사용하며, 좌표 정보인 pair를 넣을 수 있도록 해주었다.



정답 코드


#include 
<iostream>
#include 
<vector>
#include 
<queue>
#include 
<set>

using namespace std;

struct Tree
{
    Tree(int y, int x, int age)
        :y(y), x(x), age(age)
    {

    }

    int y;
    int x;
    int age;
};

struct pqCompare
{
    bool operator()(const Tree& tree1, const Tree& tree2) const
    {
        return tree1.age > tree2.age;
    }
};

struct Cell
{
    Cell() : nutrient(5)
    {

    }

    priority_queue<Tree, vector<Tree>, pqCompare> trees;
    int nutrient;
};

int main()
{
    int N, M, K;
    cin >> N >> M >> K;

    vector<vector<int>> nutrients(N, vector<int>(N));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> nutrients[i][j];

    vector<vector<Cell>> grid(N, vector<Cell>(N));
    set<pair<int, int>> treePos;

    for (int i = 0; i < M; i++)
    {
        int y, x, age;
        cin >> y >> x >> age;

        treePos.insert({y-1, x-1});
        grid[y - 1][x - 1].trees.push(Tree(y - 1, x - 1, age));
    }

    for (int year = 0; year < K; year++)
    {
        // spring
        // 자신의 나이만큼 양분을 먹고, 나이가 1 증가

        vector
<Tree> deadTrees;
        vector<pair<int, int>> erasePos;
        for (auto it = treePos.begin(); it != treePos.end(); ++it)
        {
            int y = it->first;
            int x = it->second;

            int& nutrient = grid[y][x].nutrient;

            int n = grid[y][x].trees.size();
            vector
<Tree> tempTrees;
            for (int i = 0; i < n; i++)
            {
                Tree tree = grid[y][x].trees.top();
                grid[y][x].trees.pop();

                if (tree.age <= nutrient)
                {
                    nutrient -= tree.age;
                    tree.age++;
                    tempTrees.push_back(tree);
                }
                else
                {
                    deadTrees.push_back(tree);
                }
            }

            for (const Tree& tree : tempTrees)
                grid[y][x].trees.push(tree);

            if (grid[y][x].trees.empty())
                erasePos.push_back({ y, x });
        }

        for (const pair<int, int>& pos : erasePos)
            treePos.erase(pos);

        // summer
        // 여름에는 봄에 죽은 나무가 양분으로 변하게 된다.
        // 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가
        for (const Tree& tree : deadTrees)
        {
            int add = (tree.age) / 2;
            grid[tree.y][tree.x].nutrient += add;
        }

        // fall
        // 가을에는 나무가 번식한다. 
        // 번식하는 나무는 나이가 5의 배수이어야 하며, 
        // 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
        int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
        int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};

        vector<pair<int, int>> insertPos;
        vector
<Tree> addTrees;
        for (auto it = treePos.begin(); it != treePos.end(); ++it)
        {
            int y = it->first; int x = it->second;
            int n = grid[y][x].trees.size();

            for (int i = 0; i < n; i++)
            {
                Tree savedTree = grid[y][x].trees.top();
                grid[y][x].trees.pop();

                // 번식.
                if (savedTree.age % 5 == 0)
                {
                    for (int dir = 0; dir < 8; dir++)
                    {
                        int adjY = y + dy[dir];
                        int adjX = x + dx[dir];

                        if (adjY < 0 || adjY >= N || adjX < 0 || adjX >= N)
                            continue;

                        addTrees.push_back(Tree(adjY, adjX, 1));
                        //grid[adjY][adjX].trees.push(Tree(adjY, adjX, 1));
                        insertPos.push_back({ adjY, adjX });
                    }
                }

                addTrees.push_back(savedTree);
            }
        }

        for (const Tree& tree : addTrees)
            grid[tree.y][tree.x].trees.push(tree);

        for (const pair<int, int>& pos : insertPos)
        {
            treePos.insert(pos);
        }

        // winter
        // S2D2가 땅을 돌아다니면서 땅에 양분을 추가
        for (int y = 0; y < N; y++)
            for (int x = 0; x < N; x++)
                grid[y][x].nutrient += nutrients[y][x];
    }

    int answer = 0;
    for (pair<int, int> pos : treePos)
    {
        answer += grid[pos.first][pos.second].trees.size();
    }

    cout << answer;
}

Share Article

Follow Me Written By

keipro

Other Articles

Related Posts