[BOJ] 16235 - 나무 제테크

[백준] 16234 - 인구 이동

열심히 다 구현하고 TC를 돌렸는데 TC가 제대로 안나오는 것이다. 그래서 디버깅을 했는데 내 알고리즘에서는 너무 완벽했다. 문제를 다시 읽어보니 한 칸에 여러 나무가 있을 수 있다는 것을 완전히 놓치고 풀었다. 다행히 크게 코드 변경을 하지 않고도 문제를 풀 수 있었다. 그렇지만 약간의 피눈물이 날 뻔 했다..
문제를 고치려고 하니 시간복잡도 측면에서 약간 걱정이 되어 처음에는 최소힙을 사용하려고 했다. 그러나 최소힙은 모든 원소를 확인하기 위해 필연적으로 모든 원소를 pop하고 다시 push해야하는 엄청나게 귀찮은 과정이 필요해 set으로 노선을 변경했다. 그렇지만 set은 중복 원소 삽입이 되지 않는 엄청나게 귀찮은 문제가 있었다. map으로 바꿀까 싶었지만 어차피 매 년마다 정렬은 한 번만 하면 되고 어차피 pop했다가 다시 새로 만들어서 넣는 것은 set이나 최소 힙도 마찬가지니까 그렇게 큰 차이가 없을 것 같아서 그냥 vector를 사용했다.
1은 항상 push_back으로 가장 뒤에 들어가기 때문에 내림차순 정렬이 더 빠를까 싶어 그렇게 했는데 지금 다시 보니 tmp배열이.. 자연스럽게 오름차순 배열이 되므로 역효과였을지도 모르겠다..push_front가 가능했다면..
python의 deque를 사용했다면 매번 정렬하지 않고도 구현이 가능하지 않았을까 하는 생각을 조심스레 해본다.

소스코드

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string.h>
#include <queue>
#include <set>
#include <functional>
#define INF 987654321
using namespace std;
typedef pair<int, int> PII;

const int dr[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dc[8] = { -1, 0, 1, 1, -1, -1, 0, 1 };
int n, m, k, energy[15][15], a[15][15];
vector<int> tree[15][15];

void init() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            energy[i][j] = 5;
        }
    }
}

bool is_in_range(int x, int y) {
    return x >= 0 && x < n&& y >= 0 && y < n;
}

void SpringSummer() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            bool ck = false;
            sort(tree[i][j].begin(), tree[i][j].end(), greater<int>());
            vector<int> tmp;
            for (int k = tree[i][j].size() - 1; k >= 0; k--) {
                int now = tree[i][j][k];
                if (ck) {
                    energy[i][j] += now / 2;
                }
                else if (energy[i][j] >= now) {
                    energy[i][j] -= now;
                    tmp.push_back(now + 1);
                }
                else {
                    ck = true;
                    energy[i][j] += now / 2;
                }
            }
            tree[i][j] = tmp;
        }
    }
}

void fall() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for(auto now : tree[i][j]){
                if(now % 5 == 0) {
                    for (int k = 0; k < 8; k++) {
                        int x = i + dr[k], y = j + dc[k];
                        if (is_in_range(x, y)) tree[x][y].push_back(1);
                    }
                }
            }
        }
    }
}

void winter() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            energy[i][j] += a[i][j];
        }
    }
}

int year(int k) {
    int rtn = 0;
    for (int i = 0; i < k; i++) {
        SpringSummer();
        fall();
        winter();
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            rtn += tree[i][j].size();
        }
    }
    return rtn;
}

int main(void) {
    int x, y, z;
    scanf("%d %d %d", &n, &m, &k);
    init();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", a[i] + j);
        }
    }
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &x, &y, &z);
        tree[x - 1][y - 1].push_back(z);
    }
    printf("%d", year(k));
    return 0;
}