백준 #16235 나무재테크

백준 #16235 나무재테크

단순한 구현 문제지만 제한시간이 짧아 시간복잡도를 생각해서 풀어야 하는 문제.

흐름

trees deque에는 나무들의 위치와 나이가 들어있다. 봄에 나이가 적은 나무 순서대로 양분을 흡수하는데, 그를 위해서 sort를 매번 돌리기 보단 한 번 sort한 후에 가을에 새로 생성되는 나무를 push_front()하기 위해 vector 대신 deque를 사용했다. sort를 한 번만 한 후 새로 생성되는 나무를 맨 앞에 놓으면 자동으로 정렬이 된다.

std::vector의 시간복잡도

접근: $O(1)$

맨 뒤 원소 추가/제거: $O(1)$

임의의 위치에 원소 추가/제거: $O(n)$

std::deque의 시간복잡도

접근: $O(1)$

맨 앞, 맨 뒤 원소 추가/제거: $O(1)$

임의의 위치에 원소 추가/제거: $O(n)$

또 여름이나 가을에 매번 전체 deque에서 죽은 나무나 번식할 수 있는 나무를 반복문으로 돌며 체크하는 것은 시간이 걸려서, deadTrees와 mulTrees라는 queue를 새로 만들어 봄에 해당 나무를 push하여 여름과 가을에 각각 전부 pop하며 처리를 했다.

#include <iostream>
#include <bits/stdc++.h>
#include <deque>
#include <algorithm>
#include <tuple>
#include <queue>

using namespace std;
int N, M, K;
int A[10][10];
int board[10][10];
deque<tuple<int, int, int>> trees;
queue<tuple<int, int, int>> deadTrees;
queue<pair<int, int>> mulTrees;
int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[8] = {1, 0, -1, 1, -1, 1, 0, -1};

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

void spring() {
    int n = trees.size();
    for(int i = 0; i < n; i++) {
        tuple<int, int, int> tree = trees.front();
        trees.pop_front();
        if(board[get<1>(tree)][get<2>(tree)] >= get<0>(tree)) {
            board[get<1>(tree)][get<2>(tree)] -= get<0>(tree);
            get<0>(tree)++;
            trees.push_back(tree);
            if(get<0>(tree) % 5 == 0) {
                mulTrees.push({get<1>(tree), get<2>(tree)});
            }
        } else {
            deadTrees.push(tree);
        }
    }
}

void summer() {
    while(!deadTrees.empty()) {
        board[get<1>(deadTrees.front())][get<2>(deadTrees.front())] += get<0>(deadTrees.front()) / 2;
        deadTrees.pop();
    }
}

void fall() {
    while(!mulTrees.empty()) {
        for(int i = 0; i < 8; i++) {
            int nX = mulTrees.front().first + dx[i];
            int nY = mulTrees.front().second + dy[i];
            if(isInBoard(nX, nY)) {
                trees.push_front({1, nX, nY});
            }
        }
        mulTrees.pop();
    }
}

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> K;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> A[i][j];
            board[i][j] = 5;
        }
    }
    for(int i = 0; i < M; i++) {
        int x, y, age;
        cin >> x >> y >> age;
        trees.push_back({age, x - 1, y - 1});
    }
    sort(trees.begin(), trees.end());
    for(int i = 0; i < K; i++) {
        spring();
        summer();
        fall();
        winter();
    }
    cout << trees.size();
    
    return 0;
}