16235번 : 나무제테크 - Junnnho

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

16235번: 나무 재테크

이 문제를 해결하는데 필요한 알고리즘 : 구현, BFS

 

그냥 문제에 적힌 그대로 따라가면 되는 문제이다.

sort를 잘못된 위치에 적어주면 시간초과가 발생할수 있으니,

어린 나무를 확인해야하는 봄에만 sort를 시켜주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
int N, M, K, a, b, c, temp;
int A[11][11]; // A배열은 양분을 저장할 배열
int Aarr[11][11]; // Aarr배열은 현재 양분이 저장되어 있는 배열
int x[] = { -1,-1,-1,0,0,1,1,1 };
int y[] = { -1,0,1,-1,1,-1,0,1 };
int Summer[11][11];
typedef struct _Tree {
    vector<int> tree;
};
 
_Tree Tree[11][11];
 
void spring() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (Tree[i][j].tree.size() != 0) {
                sort(Tree[i][j].tree.begin(), Tree[i][j].tree.end());
                for (int k = 0; k < Tree[i][j].tree.size(); k++) {
                    if (Aarr[i][j] >= Tree[i][j].tree[k]) {
                        Aarr[i][j] -= Tree[i][j].tree[k];
                        Tree[i][j].tree[k]++;
                    }
                    else {
                        Summer[i][j] += Tree[i][j].tree[k] / 2;
                        Tree[i][j].tree.erase(Tree[i][j].tree.begin() + k--);
                    }
                }
            }
        }
    }
}
 
void summer() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            Aarr[i][j] += Summer[i][j];
            Summer[i][j] = 0;
        }
    }
}
 
void autumn() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (Tree[i][j].tree.size() != 0) {
                for (int k = 0; k < Tree[i][j].tree.size(); k++) {
                    if (Tree[i][j].tree[k] % 5 == 0) {
                        for (int h = 0; h < 8; h++) {
                            if (i + x[h] > 0 && i + x[h] <= N && j + y[h] > 0 && j + y[h] <= N) {
                                Tree[i + x[h]][j + y[h]].tree.push_back(1);
                            }
                        }
                    }
                }
            }
        }
    }
}
 
void winter() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            Aarr[i][j] += A[i][j];
        }
    }
}
 
int main() {
    scanf("%d%d%d", &N, &M, &K);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &A[i][j]);
            Aarr[i][j] = 5;
        }
    }
    for (int i = 0; i < M; i++) {
        scanf("%d%d%d", &a, &b, &c);
        Tree[a][b].tree.push_back(c);
    }
    while (K--) {
        spring(), summer(), autumn(), winter();
    }
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            temp += Tree[i][j].tree.size();
 
    printf("%d", temp);
    return 0;
}