[ 백준 16235 ] 나무 재태크 (C++) - 자료구조

---

🔗 문제 링크

16235번: 나무 재테크

---

💡 문제 풀이 및 해석

1. 봄 -> 여름 -> 가을 -> 겨울 순으로 구현하면 된다. 다른 점은 없다.
2. 상도의 땅 정보를 받을 수 있는 구조를 struct를 통해 만들어준다.
3. 봄에 양분을 못먹은 나무는 여름에 죽고 양분이 된다. -> 봄과 여름을 연관성있게 코드를 짜면 시간을 단축할 수 있다.
4. 번식할 수 있는 나무는 5의 배수다. -> 5의 배수인 나무만 따로 체크해두면, 모든 나무를 검사할 필요가 없다. (번식한 나무가 죽는 것도 아니기 때문에, 따로 리스트만 만들어주면 된다.)
5. 마지막으로, 겨울에 영양분을 추가해주면 끝이다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<deque>

using namespace std;

struct Node
{
    int energy = 5;
    int canBreed = 0; // 번식할 수 있는 나무들 수
    deque<int> q; // 칸에 심어진 나무들
};

int N, M, K;
Node MAP[11][11]; // 상도의 땅 정보
int supply[11][11]; // 겨울철 영양 공급
int Next[8][2] = { {-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1},{-1,0} };
void init() {
    cin >> N >> M >> K;
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            cin >> supply[y][x];
        }
    }
    for (int i = 0; i < M; i++) {
        int y, x, z;
        cin >> y >> x >> z;
        MAP[y][x].q.push_back(z); // 좌표에 어린 나무부터 영양분을 먹게 심음.
    }
}
void spring() {
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            deque<int> newTree;
            bool isSummer = false;
            while (!MAP[y][x].q.empty()) {
                int tree = MAP[y][x].q.front();
                MAP[y][x].q.pop_front();
                if (isSummer) { // 여름엔 양분을 못먹은 나무가 죽는다.
                    MAP[y][x].energy += (tree / 2);
                    continue;
                }
                if (tree <= MAP[y][x].energy) {
                    MAP[y][x].energy -= tree; // 나무의 나이만큼 영양분을 먹는다.
                    tree += 1; // 나무는 나이+1
                    if (tree % 5 == 0) MAP[y][x].canBreed++; // 번식 할 수 있는 나무는 따로 또 저장
                    newTree.push_back(tree); // 나이가 많은 나무는 뒤로
                }
                else { // 더 이상 양분을 먹을 수 있는 나무가 없다면 여름에 죽고 양분이 된다.
                    isSummer = true;
                    MAP[y][x].energy += (tree / 2);
                }
            }
            MAP[y][x].q = newTree;
        }
    }
}
void autumn() {
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            for (int i = 0; i < 8; i++) { // 주변으로 번식
                int nx = x + Next[i][0];
                int ny = y + Next[i][1];
                if (nx > 0 && ny > 0 && nx <= N && ny <= N) {
                    for (int i = 0; i < MAP[y][x].canBreed; i++) {
                        MAP[ny][nx].q.push_front(1); // 나이가 어린 순으로 먼저 양분을 먹게 삽입
                    }
                }
            }
            MAP[y][x].canBreed = 0; // 번식할 수 있는 나무 초기화
        }
    }
}
void winter() {
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            MAP[y][x].energy += supply[y][x];
        }
    }
}
void sol() {
    while (K--) {
        spring();
        autumn();
        winter();
    }
    int livingTree = 0;
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            livingTree += MAP[y][x].q.size();
        }
    }
    cout << livingTree;
}
int main() {
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    init();
    sol();
    return 0;
}

---

❎ 다른 풀이 오답 링크 - 시간초과

BaekJoon_16235, 나무 재테크 | Notion

---

🤔 문제 후기

처음에는 시간초과로 틀렸는데, deque가 아닌 pq로 풀었기 때문이다. 나무의 나이가 항상 정렬되고, 삽입할 때마다 정렬해줘야 한다고 생각했지만, 번식한 나무만 deque를 사용해서 앞에 push 해주면, 자동으로 정렬되는 문제였다. pq는 삽입할 때, O(N)이 걸리는 반면, deque는 O(1) 이기 때문에, 당연히 시간적으로 많은 차이가 날 수밖에 없었는데, 너무 구현만 생각한 것 같다. 문제 자체가 어렵진 않았지만, '나무의 나이가 어린 순서' 라는 키워드에 너무 집중한 나머지 정렬을 해야한다고 생각한게 문제였던 것 같다.