[백준] 16235번: 나무 재테크

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

16235번: 나무 재테크

문제의 구현은 생각보다 간단하지만, 시간 초과가 계속 발생해서 문제를 조금 더 효율적으로 풀도록 노력해야 하는 문제이다.

다행히 코드 디자인을 수정하기에 용이하게 해둔 덕분에 수정이 어렵지는 않았다.

여기서 시간이 많이 소요될 수 있는 부분은 다음과 같다.

• 죽은 나무를 걸러내는 작업
• 어린 나무부터 정렬하는 작업

문제 질문 게시판을 보면 deque를 쓰는 경우가 많았으나, 나는 이 문제가 deque를 쓰지 않고 풀어보았다.

그리고 priority queue를 쓸까도 고민했는데, 오히려 잦은 삽입으로 시간이 더 많이 소요될 수 있다는 생각이 들었다.

보통의 자료구조는 삽입 시 시간 복잡도가 $O(1)$이나 priority queue의 경우 $O(log n)$이라는 시간 복잡도가 평균적으로 소요된다.

왜냐하면 매년 2번 정도 나무를 모조리 탐색해야하기 때문에 상당히 비효율적인 자료구조라고 생각했다.

그래서 삽입마다 정렬이 이루어지는 것보다, 최대한 삽입 시의 순서를 유지하면서 정렬된 상태를 파악할 수 있도록 했다.

 

그렇게 떠오른 방식이 앞에서부터 새로 번식된 나무를 삽입하는 것이다.

만약 뒤에서부터 새로 번식한 나무를 삽입하고 뒤에서부터 접근하면서 담기 시작하면 결과적으로 남는 배열은 새로 번식한 나무가 앞에 와있게 된다. 그러면 오름차순과 내림차순이 번갈아 나타나기 때문에 문제 풀이가 복잡해진다.

 

그래서 벡터의 앞부터 새로 번식한 나무를 넣고 그 다음에 기존의 나무를 넣는 식으로 정렬을 유지할 수 있도록 했다.

 

그 과정에서 deep copy가 발생하면서 O(N) 이라는 시간 복잡도를 사용하였으나, 최소 $O(NlogN)$이라는 시간복잡도로 매번 정렬하는 것보다는 효율적이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int dr[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dc[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
struct Tree {
    int age;
    bool living;
    int r;
    int c;
};
int n, m, k;
vector<Tree> trees;
queue<Tree> dead;
bool cmp(Tree& a, Tree& b) {
    return a.age < b.age;
}
bool inside(int r, int c) {
    return r >= 0 && r < n&& c >= 0 && c < n;
}
void spring(vector<vector<int>>& nutrition) {
    vector<Tree> living_trees;
    for (int i = 0; i < trees.size(); i++) {
        int r = trees[i].r;
        int c = trees[i].c;
        int age = trees[i].age;
        if (nutrition[r][c] < age) {
            dead.push(trees[i]);
        }
        else {
            nutrition[r][c] -= trees[i].age++;
            living_trees.push_back(trees[i]);
        }
    }

    trees = living_trees;
}
// 산 나무만 남기기
void summer(vector<vector<int>>& nutrition) {
    while (!dead.empty()) {
        auto tree = dead.front();
        dead.pop();
        int r = tree.r;
        int c = tree.c;

        nutrition[r][c] += tree.age / 2;
    }
}

void autumn() {
    vector<Tree> new_trees;
    for (int i = 0; i < trees.size(); i++) {
        if (trees[i].age % 5 == 0) {
            for (int d = 0; d < 8; d++) {
                int nr = trees[i].r + dr[d];
                int nc = trees[i].c + dc[d];

                if (inside(nr, nc)) {
                    new_trees.push_back(Tree{ 1, true, nr, nc });
                }
            }
        }
    }

    for (int i = 0; i < trees.size(); i++) {
        new_trees.push_back(trees[i]);
    }
    trees = new_trees;
}

void winter(vector<vector<int>>& nutrition, vector<vector<int>>& a) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            nutrition[i][j] += a[i][j];
        }
    }
}
int main() {
    cin >> n >> m >> k;

    vector<vector<int>> nutrition(n, vector<int>(n, 5));
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        trees.push_back(Tree{ z, true, x - 1, y - 1 });
    }

    for (int i = 0; i < k; i++) {
        spring(nutrition);
        summer(nutrition);
        autumn();
        winter(nutrition, a);
    }


    cout << trees.size() << '\n';
}