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

이 포스트는 백준 사이트의 나무 재테크 문제 풀이입니다.

문제

해결 과정

처음 이 문제를 접하였을 때, 우선순위 큐(priority_queue)를 활용해서 풀어보가자 하였습니다.

C++에서 우선순위 큐는 최대힙을 사용하기 때문에 상수시간으로 최댓값에 접근할 수 있습니다.
그러나 최대힙은 균형이진트리 이기 때문에 삽입과 삭제가 빈번하게 발생하면
균형을 맞추기위한 힙의 연산으로 실행시간이 늘어날 수 있습니다.

때문에 우선순위 큐를 활용한 첫 번째 코드에서는 시간초과가 발생했습니다.

1차 시도 (실패)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct POINT {
    int age, row, col;

    bool operator<(const POINT& rhs) {
        return this->age > rhs.age;
    }
};

struct Comp {
    bool operator()(const POINT& lhs, const POINT& rhs) {
        return lhs.age > rhs.age;
    }  
};

int N, M, K;
vector<vector<int>> A(11, vector<int>(11, 0));
vector<vector<int>> ground(11, vector<int>(11, 5));
vector<vector<int>> next_ground;

int dir_row[8]{-1, -1, 0, 1, 1, 1, 0, -1};
int dir_col[8]{0, 1, 1, 1, 0, -1, -1, -1};

priority_queue<POINT, vector<POINT>, Comp> tree_q;

void input() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M >> K;
    for(int row = 1; row <= N; ++row) {
        for(int col = 1; col <= N; ++col) {
            cin >> A[row][col];
        }
    }

    for(int i = 0, row, col, age; i < M; ++i) {
        cin >> row >> col >> age;
        tree_q.push({age, row, col});
    }
}

queue<POINT> dead_tree_q;
priority_queue<POINT, vector<POINT>, Comp> next_tree_q;

bool spend_year() {
    if(tree_q.empty()) return false;

    next_ground = ground;
    
    while(false == tree_q.empty()) {
        auto tree = tree_q.top();
        tree_q.pop();
        
        if(next_ground[tree.row][tree.col] >= tree.age) {
            next_ground[tree.row][tree.col] -= tree.age;
            tree.age += 1;
            next_tree_q.push(tree);
        } else {
            dead_tree_q.push(tree);
        }
    }

    while(false == dead_tree_q.empty()) {
        auto tree = dead_tree_q.front();
        dead_tree_q.pop();

        next_ground[tree.row][tree.col] += (tree.age / 2);
    }

    priority_queue<POINT, vector<POINT>, Comp> family_tree_q;
    while(false == next_tree_q.empty()) {
        auto tree = next_tree_q.top();
        next_tree_q.pop();

        tree_q.push(tree);
        if(tree.age % 5 == 0) {
            for(int dir = 0; dir < 8; ++dir) {
                int new_row = tree.row + dir_row[dir];
                int new_col = tree.col + dir_col[dir];

                if(new_row < 1 || new_row > N || new_col < 1 || new_col > N)
                    continue;
                tree_q.push({1, new_row, new_col});
            }
        }
    }

    for(int row = 1; row <= N; ++row) {
        for(int col = 1; col <= N; ++col) {
            next_ground[row][col] += A[row][col];
        }
    }

    ground = next_ground;
    return true;
}

int main() {
    input();

    for(int year = 0; year < K; ++year) {
        if(false == spend_year()) break;
    }

    printf("%d", tree_q.size());

    return 0;
}

2차 시도 (성공)

실행 시간을 줄이기 위해서 여러 방법을 시도하던 중
N 의 최대크기가 10 이라는 것을 통해 완전탐색이 가능하다는 것을 알게 되었습니다.
따라서 2번째 시도에서는 모든 땅을 완전탐색하여 정답을 출력할 수 있었습니다.

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 11

using namespace std;

struct POINT {
    int row, col, age;
};

int N, M, K;
vector<vector<int>> A(MAX, vector<int>(MAX, 0));
vector<int> trees[MAX][MAX];
vector<vector<int>> ground(MAX, vector<int>(MAX, 5));
vector<vector<int>> next_ground;

int dir_row[8]{-1, -1, 0, 1, 1, 1, 0, -1};
int dir_col[8]{0, 1, 1, 1, 0, -1, -1, -1};

void input() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M >> K;
    for(int row = 1; row <= N; ++row) {
        for(int col = 1; col <= N; ++col) {
            cin >> A[row][col];
        }
    }

    for(int i = 0, row, col, age; i < M; ++i) {
        cin >> row >> col >> age;
        trees[row][col].push_back(age);
    }
}

void spend_year() {
    for(int row = 1; row <= N; ++row) {
        for(int col = 1; col <= N; ++col) {
            if(trees[row][col].empty()) {
                continue;
            }

            sort(trees[row][col].begin(), trees[row][col].end());

            vector<int> new_trees;
            int add_ground_energe = 0;
            for(auto tree_age : trees[row][col]) {
                if(ground[row][col] >= tree_age) {
                    ground[row][col] -= tree_age;
                    new_trees.push_back(tree_age + 1);
                } else {
                    add_ground_energe += (tree_age / 2);
                }
            }

            trees[row][col] = new_trees;
            ground[row][col] += add_ground_energe;
        }
    }

    for(int row = 1; row <= N; ++row) {
        for(int col = 1; col <= N; ++col) {
            if(trees[row][col].empty()) {
                continue;
            }
            
            for(auto tree_age : trees[row][col]) {
                if(tree_age % 5 == 0) {
                    for(int dir = 0; dir < 8; ++dir) {
                        int new_row = row + dir_row[dir];
                        int new_col = col + dir_col[dir];

                        if(new_row < 1 || new_row > N || new_col < 1 || new_col > N)
                            continue;
                        trees[new_row][new_col].push_back(1);
                    }
                }
            }
        }
    }

    for(int row = 1; row <= N; ++row) {
        for(int col = 1; col <= N; ++col) {
            ground[row][col] += A[row][col];
        }
    }
}

int get_alive_tree() {
    int answer = 0;
    for(int row = 1; row <= N; ++row) {
        for(int col = 1; col <= N; ++col) {
            answer += trees[row][col].size();
        }
    }
    return answer;
}

int main() {
    input();

    for(int year = 0; year < K; ++year) {
        spend_year();
    }

    int alive_tree_cnt = get_alive_tree();
    printf("%d", alive_tree_cnt);

    return 0;
}

실행 결과