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

16235번: 나무 재테크

생각보다 시간이 오래걸린 구현 문제였다. 봄, 여름, 가을, 겨울을 K만큼 돌면서 마지막에 남은 나무의 갯수를 구하면 되는 문제이다. 조건들이 굉장히 많이 나오는데 유심히 봐야한다. 나는 처음에 모든 칸에 양분을 5만큼 준다는 조건을 보지 못해 많이 해맸었다. 칸마다 나무가 여러개 있을 수 있고 양분은 나이가 어린 나무부터 먹기 때문에 앞 뒤로 값을 추가, 제거 할 수 있는 deque를 사용했다. 계절마다 조건에 맞춰 반복문을 돈 후, deque에 남아있는 나무의 개수를 모두 더해 출력해주었다. 사실 처음에는 deque가 아닌 vector를 사용하여 sort하여 나이순으로 정렬을 해주면서 반복문을 진행했는데 당연하게도 시간 초과가 났었다. 질문게시판을 통해 deque를 사용하면 sort 없이도 가능하다는 것을 알았다. vector만 사용하는 버릇을 고쳐야겠다.

#include <iostream>
#include <queue>
#include <deque>

using namespace std;

int N, M, K, res = 0;
int A[10][10];
int G[10][10];
deque<int> d[10][10];
queue<pair<pair<int, int>, int>> die;
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };

void spring() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int s = d[i][j].size();

            for (int k = 0; k < s; k++) {
                int age = d[i][j].front();
                d[i][j].pop_front();

                if (G[i][j] - age < 0) {
                    die.push({ {i,j},age });
                }
                else {
                    d[i][j].push_back(age + 1);
                    G[i][j] -= age;
                }
            }
        }
    }
}

void summer() {
    while(!die.empty()) {
        int y = die.front().first.first;
        int x = die.front().first.second;
        int age = die.front().second;

        die.pop();

        G[y][x] += + age / 2;
    }
}

void fall() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < d[i][j].size(); k++) {
                if (d[i][j][k] % 5 != 0) continue;

                for (int l = 0; l < 8; l++) {
                    int ny = i + dy[l];
                    int nx = j + dx[l];

                    if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;

                    d[ny][nx].push_front(1);
                }
            }
        }
    }
}

void winter() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            G[i][j] += A[i][j];
        }
    }
}

void solution() {
    for (int i = 0; i < K; i++) {
        spring();
        summer();
        fall();
        winter();
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            res += d[i][j].size();
        }
    }

    cout << res;
}

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

    cin >> N >> M >> K;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
            G[i][j] = 5;
        }
    }

    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        d[a - 1][b - 1].push_back(c);
    }

    solution();

    return 0;
}