백준 16235 나무 재테크(C++)

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

 

구현 자체도 정신을 똑바로 차려야하고 0.3초라는 매우 적은 시간 제한으로 인해 최적화를 잘 해줘야했다.

 

각 땅의 상황을 계절에 맞게 조절하는 것이 관건인 문제였다. 그리고 한 타일에 나무가 여러그루를 잘 컨트롤해줘야 했다. 나의 경우 2차원 자료구조를 사용하기 싫어서 1차원으로 사용후 x, y 좌표를 변화해주는 작업을 했는데 지금 생각하니 굳이 필요없는 작업인 것 같다.

 

이 문제에서 핵심은 N <= 10 이기 때문에 타일을 순회하는 것은 그렇게 큰 시간이 들지 않지만 한 타일의 모든 나무들을 컨트롤 해줄 때 시간을 어떻게 최적화할 수 있느냐가 핵심이었다. 

 

조건에서 여러 나무가 있다면 나이가 가장 어린 순서대로 처리해주어야하기 때문에 처음엔 우선순위 큐를 사용했다.

 

예제는 모두 통과했지만 43퍼센트에서 시간초과가 발생했다. 그리고 질문게시판과 구글링을 통해 우선순위큐가 아닌 덱이 답이라는 것을 알았다.

 

문제에서 나무가 번식하면 무조건 나이는 1이다. 그리고 조건상 반드시 여름부턴 모든 나무의 나이가 2 이상이 된다. 그러므로 굳이 우선순위 큐를 사용할 필요가 없다. 이미 순서는 정해져있기 때문이다. 그래서 덱을 사용한다. 덱은 양방향으로 값을 넣을 수 있기 때문에 번식으로 인해 처음 들어오는 자식 나무라면 front에 삽입해주면 나이 어린 순서대로 처리가 가능하다.

 

우선순위 큐의 insert와 pop은 O(log(N))

덱의 insert, pop은 O(1) 

 

이다.

 

#include <iostream>
#include <map>
#include <queue>
using namespace std;
int nutron[101][101];
int ground[101][101];
deque<int> tree[101];
int deadTree[101][101];

int dx[] = {0,0,1,-1,1,-1,1,-1};
int dy[] = {1,-1,0,0,1,-1,-1,1};
int N, M, K;

void print_ground(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cout << ground[i][j] << ' ';
        }
        cout << endl;
    }
}

void spring_summer(){
    for(int i = 0; i < N * N; i++){
        if(tree[i].size() == 0) continue;

        deque<int> tmpQueue;
        int x = i / N;
        int y = i % N;
        while(!tree[i].empty()){
            int treeAge = tree[i].front();
            if(ground[x][y] < treeAge){ // 나무 죽음
                deadTree[x][y] += (treeAge / 2);
            }else{
                ground[x][y] -= treeAge;
                tmpQueue.push_back( (treeAge + 1) );
            }

            tree[i].pop_front();
        }

        ground[x][y] += deadTree[x][y];
        deadTree[x][y] = 0;

        tree[i] = tmpQueue;
    }
}

bool range(int x, int y){
    return x > -1 && x < N && y > -1 && y < N;
}

void fall(){
    for(int i = 0; i < N * N; i++){
        if(tree[i].size() == 0) continue;

        deque<int> tmpQueue;

        while(!tree[i].empty()){
            tmpQueue.push_back(tree[i].front());
            int treeAge = tree[i].front();
            tree[i].pop_front();
            if(treeAge % 5 != 0) continue;
            int x = i / N;
            int y = i % N;
            for(int i = 0; i < 8; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(range(nx, ny)){
                    tree[nx * N + ny].push_front(1);
                }
            }
        }

        tree[i] = tmpQueue;
    }
}

void winters(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            ground[i][j] += nutron[i][j];
        }
    }
}

int answer(){
    int ans = 0;
    for(int i = 0; i < N * N; i++) ans += tree[i].size();

    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> K;
    int idx = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> nutron[i][j];
            ground[i][j] = 5;
            
            idx++;
        }
    }

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

        x--;
        y--;

        tree[x * N + y].push_back(age);
    }

    for(int i = 0; i < K; i++){
        spring_summer();
        fall();
        winters();
    }

    cout << answer() << '\n';
}