📃 문제
[BOJ] 소문난 칠공주 🔗링크
❓ 문제 접근
🧠 풀이
#include <iostream>
#include <deque>
#include <utility>
#include <algorithm>
using namespace std;
int supply[11][11] = {0,};
int food[11][11] = {0,};
deque<pair<pair<int,int>,int>> trees;
deque<pair<pair<int,int>,int>> deadTrees;
deque<pair<pair<int,int>,int>> breedingTrees;
int dx[8] = {-1,0,1,1,1,0,-1,-1};
int dy[8] = {-1,-1,-1,0,1,1,1,0};
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0);
cin.tie(0);
int N,M,K;
cin >> N >> M >> K;
for(int r=0; r<N; r++){
for(int c=0; c<N; c++){
cin >> supply[r][c];
food[r][c] = 5;
}
}
for(int i=0; i<M; i++){
int x,y,z;
cin >> x >> y >> z;
trees.push_back({{x-1,y-1},z});
}
sort(trees.begin(), trees.end());
for(int year=0; year<K; year++){
int treeCount = trees.size();
for(int i=0; i<treeCount; i++){
int x = trees.front().first.first;
int y = trees.front().first.second;
int age = trees.front().second;
trees.pop_front();
if(food[x][y] >= age){
trees.push_back({{x,y},age+1});
food[x][y] -= age;
}
else{
deadTrees.push_back({{x,y,},age});
}
}
while(!deadTrees.empty()){
int x = deadTrees.front().first.first;
int y = deadTrees.front().first.second;
int age = deadTrees.front().second;
deadTrees.pop_front();
food[x][y] += age / 2;
}
treeCount = trees.size();
for(int i=0; i<treeCount; i++){
int x = trees[i].first.first;
int y = trees[i].first.second;
int age = trees[i].second;
if(age%5 == 0){
for(int dir=0; dir<8; dir++){
int nx = x + dx[dir];
int ny = y + dy[dir];
if(!(nx>=0 && nx<N && ny>=0 && ny<N)) continue;
breedingTrees.push_back({{nx,ny},1});
}
}
}
while(!breedingTrees.empty()){
trees.push_front(breedingTrees.front());
breedingTrees.pop_front();
}
for(int r=0; r<N; r++){
for(int c=0; c<N; c++){
food[r][c] += supply[r][c];
}
}
}
cout << trees.size();
return 0;
}