[백준 16235 C++][G4] 나무 재테크

⭐️ 난이도

 

Gold 4

---

⭐️ 문제

https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

 

 

---

⭐️ Idea flow

 

봄, 여름, 가을, 겨울마다 어떤 일이 일어나는지 문제에서 주어지기 때문에 이를 잘 구현하면 되는 구현&시뮬레이션 문제였다.

주의할 점은 시간 제한이 0.3초인 것이었는데, 구현을 하는 과정에서 반복문과 정렬(소팅)이 필요해서 이를 적절히 배치해야했다.

 

[처음 생각했던 풀이 - 시간 초과]

우선 나무의 나이, y 좌표, x 좌표를 변수로 갖는 class Tree를 선언한다.

현재 땅의 양분 상태를 나타내는 변수 grid, 겨울마다 추가하는 양분의 정보를 담는 변수 supply, 봄마다 죽는 나무를 임시 저장할 변수 tmp, 그리고 나무의 정보를 담는 변수 tree를 선언한다.

 

나무의 정보를 vector 안에 담아서 한 번에 관리하는 것을 생각했는데, 나무의 나이가 적은 순으로 정렬만 된다면 상관없기 때문이다.

그리고 문제에서 주어진대로 봄, 여름, 가을, 겨울을 한 사이클로 하여 이 사이클을 총 k번 실행하고, 봄을 실행하기 전에 항상 변수 tree를 age(나이)를 기준으로 정렬을 실행했다.

 

하지만 이렇게 하니 시간 초과가 나왔고 해결하기 위해 시간을 썼으나, 결국 해결책을 찾지 못해 질문 게시판의 도움을 받았다.

 

 

[시간 초과를 해결한 풀이]

윗 풀이를 생각하면서도 반복문과 sort 함수가 불안했는데, 이 때문에 시간 초과가 난다고 한다.

이를 해결하기 위한 방법이 있는데

 

1) 먼저 기존에는 봄, 여름, 가을, 겨울을 순서대로 실행했는데, 봄을 진행하면서 가을도 같이 처리할 수가 있었다.

   나무가 양분을 먹고 나이를 먹은 후에 나이를 확인해서 5의 배수이면 해당 위치의 인접한 8칸에 나무를 미리 심을 수 있다.

 

2) 나무의 나이가 항상 정렬되어 있다면 매 사이클마다 sort를 실행하지 않아도 된다. 

   vector를 두 개 선언하여 하나에는 현재 살아있는 나무(now)들을, 다른 하나에는 다음 년도에 태어날 나무(next)들을 넣는다.

   봄을 진행할 때 현재 살아있는 나무가 들어있는 vector를 순회하면서

   만일 나무가 양분을 흡수 할 수 없다면(죽는다면), 나이에 -1을 곱해 음수로 만들어 죽은 나무로 체크해놓는다.

  만일 나무가 양분을 흡수 할 수 있다면, 해당 위치의 양분을 먹고 나이를 1 더한다. 만일 나이가 5의 배수가 된다면 인접한 8칸에 대해 새로운 나무의 정보를 next 변수(다음년도에 태어날 나무)에 미리 넣어놓는다.

 

   이후에 now와 next의 내용을 서로 바꾸고, next 변수를 clear 시켜주면 된다.

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>

using namespace std;

// 16235 - 나무 재테크
struct Tree{
    int age, y, x;
};
int n, m, k;
int idx = 0;
int dy[8] = {0, -1, -1, -1, 0, 1, 1, 1}, dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
vector<vector<Tree>> tree; // 나무의 정보
vector<vector<int>> grid, supply; // 기본 땅, 겨울마다 양분 공급

void input(){
    cin >> n >> m >> k;

    tree.assign(2, vector<Tree>{});
    grid.assign(n , vector<int> (n, 5));
    supply.assign(n , vector<int>(n, 0));

    for(int i = 0; i < n; i++){
        for(int k = 0; k < n; k++){
            cin >> supply[i][k];
        }
    }

    for(int i = 0; i < m; i++){
        int x, y, z;
        cin >> y >> x >> z;
        Tree tmp = {z, y - 1, x - 1};
        tree[idx].emplace_back(tmp);
    }
}

bool compare(const struct Tree &t1, const struct Tree &t2){
    return t1.age < t2.age;
}

bool isInside(int y, int x){
    return (0 <= x && x < n) && (0 <= y && y < n);
}

void summer(vector<Tree> &now, vector<Tree> &next){
    // 봄에 죽은 나무가 나이/2만큼 해당 땅에 양분을 제공한다.
    for(int i = 0; i < now.size(); i++){
        if(now[i].age < 0){ // 죽은 나무라면 양분 추가
            grid[now[i].y][now[i].x] += -now[i].age / 2;
        }
        else{
            next.emplace_back(now[i]);
        }
    }
}

void winter(){
    for(int i = 0; i < n; i++){
        for(int k = 0; k < n; k++){
            grid[i][k] += supply[i][k];
        }
    }
}

void Cycle(){
    vector<Tree> &now = tree[idx];
    vector<Tree> &next = tree[1 - idx];
    next.clear();

    // 봄 : 모든 나무가 있는 위치에 양분이 충분히 있다면 나무가 자라고, 양분이 없다면 나무가 죽는다.
    for(int i = 0; i < now.size(); i++){
        int cy = now[i].y;
        int cx = now[i].x;

        if(now[i].age <= grid[cy][cx]){ // 양분이 충분할 때
            grid[cy][cx] -= now[i].age;
            now[i].age++;

            if(now[i].age % 5 == 0){ // 나이가 5의 배수일 때에만 번식
                for(int k = 0; k < 8; k++){ // 가을에 태어날 나무들 미리 push
                    int ny = cy + dy[k];
                    int nx = cx + dx[k];
                    if(isInside(ny, nx)){
                        next.push_back({1, ny, nx});
                    }
                }
            }
        }
        else{ // 양분이 충분하지 않을 때 죽은 나무로 표시한다.
            now[i].age = -now[i].age;
        }
    }

    summer(now, next);
    winter();

    idx = 1 - idx;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    sort(tree[idx].begin(), tree[idx].end(), compare);
    while(k--){
        Cycle();
    }

    cout << tree[idx].size();

    return 0;
}

 

---

⭐️ Feedback

 

1) 구조체를 비교하고 싶을 때엔 비교 함수를 선언하자!

 

구조체 Tree를 만들고 나서 sort 함수를 진행할 때, 따로 비교 함수를 만들어주지 않아도 제일 앞에 있는 값을 통해 정렬을 실행할 줄 알았다.

하지만 원소가 int형 세 개이기 때문에 따로 비교 함수를 만들어주어야 했다.

 

 

2) 시뮬레이션 문제에서 너무 정직하게 풀지 말자!

 

이번 문제를 풀면서 봄, 여름, 가을, 겨울을 착실하게 나누고 지문에 나와있는 그대로 구현을 했다.

하지만 이렇게 하니 효율성 부분에서 문제가 생길 수 밖에 없었던 것 같다.

합칠 수 있는 부분은 합치고, 컨테이너를 좀 더 다양하게 사용해야겠다.