백준 16235번 - 나무 재테크

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

문제에서 정의된 요구사항대로 구현을 하면 된다.

봄,여름,가을,겨울 순으로 작업을 해줘야 하는데 문제에 제시된 내용을 제대로 보지 않으면 

어디서 잘못되었는지 확인하는데 시간이 오래 걸릴 수 있다.

나의 경우, 초기의 양분값을 모두 5로 설정해야하는데

추가되는 양분의 양을 초기의 양분값으로 설정하는 실수로 30분을 날렸다...

그리고 중요한게 처음 이 문제를 접하고 아예 모든 나무의 나이 정보를 

우선순위큐에 담아서 나이 순으로 맵의 양분 정보와 죽은 나무를 업데이트하는 식으로 문제를 풀었는데 시간초과가 났다.

고민을 하다가 우선순위큐에서 계속 소팅을 하기 때문에 시간 초과가 났다고 판단하고

vector<int> tree[r][c]와 같은 식으로 (r,c)의 좌표에 나무가 있을 때 나이를 추가해주는 식으로 풀었더니 패스할 수 있었다.

수 많은 나무가 있을 때, 하나의 나무가 추가되면 모든 나무를 거쳐서 소팅 작업이 이루어지기 때문에

해당 좌표에서만 나무를 추가해주고 그 좌표에서만 소팅해주는 것이 중요하다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
 
int N, M, K;
int dy[8] = { -1,-1,-1,0,0,1,1,1 };
int dx[8] = { -1,0,1,-1,1,-1,0,1 };
struct str {
    int y;
    int x;
    int age;
    str(int y, int x, int age) :y(y), x(x), age(age) {};
};
 
int main() {
    
    std::ios_base::sync_with_stdio(false);
    
    cin >> N >> M >> K;
    
    vector<vector<int>> A(N + 1, vector<int>(N + 1,0)); // 추가되는 양분의 양
    vector<vector<int>> map(N + 1, vector<int>(N + 1,0)); //양분 정보
    vector<int> tree[11][11]; //나무의 나이 정보
    
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) {
            cin >> A[i][j];
            map[i][j] = 5;
        }
    
    
    int r, c, age;
    for (int i = 1; i <= M; i++) {
        cin >> r >> c >> age;
        tree[r][c].push_back(age);
    }
    
    while (K--) {
        
        vector<str> dead_tree; //죽은 나무
        vector<str> growth_tree; //번식 나무
        
        //봄
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                if (tree[r][c].empty())
                    continue;
                
                vector<int> vec;
                sort(tree[r][c].begin(), tree[r][c].end());
                for (int k = 0; k < tree[r][c].size(); k++) {
                    age = tree[r][c][k];
                    
                    if (map[r][c] >= age) {
                        map[r][c] -= age;
                        vec.push_back(age + 1);
                        
                        if ((age + 1) % 5 == 0)
                            growth_tree.push_back(str(r, c, age + 1));
                    }
                    else {
                        dead_tree.push_back(str(r, c, age / 2));
                    }
                }
                
                tree[r][c] = vec;
            }
        }
        
        
        //여름(죽은 나무 양분 먹는다)
        for (int i = 0; i < dead_tree.size(); i++) {
            r = dead_tree[i].y;
            c = dead_tree[i].x;
            age = dead_tree[i].age;
            
            map[r][c] += age;
        }
        
        
        //가을(번식하는 나무)
        for (int i = 0; i < growth_tree.size(); i++) {
            
            r = growth_tree[i].y;
            c = growth_tree[i].x;
            
            for (int j = 0; j < 8; j++) {
                int ny = r + dy[j];
                int nx = c + dx[j];
                
                if (ny<1 || ny>N || nx<1 || nx>N)
                    continue;
                
                tree[ny][nx].push_back(1);
            }
        }
        
        //겨울(양분 추가)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                map[i][j] += A[i][j];
        
    }
    
    int ans = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            ans += tree[i][j].size();
    
    cout << ans << endl;
    return 0;
}