[구현] 백준 16235번 나무재테크
업데이트:
문제에서 주어진대로 정말 그대로 구현했다.
각 계절을 함수로 구현하였으며, 문제에 필요한 변수 및 배열들은 모두 전역변수로 선언하였다.
땅 한 칸은 soil 이라는 구조체로 만들었고, 전체 땅은 soil 배열을 통해 만들었다.
soil 배열은 다음과 같다.
struct soil{
int tree_num;
deque<int> forest;
};
처음에는 STL 의 list를 이용했는데, list는 특정 위치의 원소를 제거하거나 추가하는 연산은 빠르지만, 전체적인 수행 시간이 느리기 때문에 시간 초과가 발생하여 list와 구현 방식이 다를 뿐 똑같이 이용할 수 있는 deque를 사용하였다.
-
봄
void spring(){ for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ if(ground[i][j].tree_num > 0){ deque<int>::iterator tmp = ground[i][j].forest.begin(); for(auto& x:ground[i][j].forest){ energy[i][j] -= x; if(energy[i][j] < 0){ energy[i][j] += x; break; } x++; tmp++; } while(tmp != ground[i][j].forest.end()){ totalTree--; ground[i][j].tree_num--; deadEnergy[i][j] += *tmp / 2; tmp = ground[i][j].forest.erase(tmp); } } } } }봄에는 나무들이 양분을 먹고 나이를 한 살 더 먹는다.
전체 땅의 양분은 energy 배열을 통해 구현하여 양분을 추가하거나 감소했다.
만약 땅의 양분이 현재 나무가 먹어야할 양분보다 적다면 반복문을 탈출하고, 해당 나무를 포함한 양분을 먹지 못한 모든 나무는 죽게 된다. 죽은 나무는 양분이 되기 때문에 미리 양분을 계산하여 deadEnergy 배열에 저장한다.
-
여름
void summer(){ for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ energy[i][j] += deadEnergy[i][j]; deadEnergy[i][j] = 0; } } }여름에는 죽은 나무들이 양분이 된다. 봄에 나무가 죽을 때 저장해놓았던 deadEnergy 배열을 통해 땅에 양분을 더해준다.
-
가을
void fall(){ for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ if(ground[i][j].tree_num > 0){ for(auto &x:ground[i][j].forest){ if(x%5==0){ for(int k=0;k<8;k++){ int temp_y = i+y_iter[k]; int temp_x = j+x_iter[k]; if(temp_y>0 && temp_x >0 && temp_y <= N && temp_x <=N){ ground[temp_y][temp_x].forest.push_front(1); totalTree++; ground[temp_y][temp_x].tree_num++; } } } } } } } }가을에는 나무들이 번식한다. 모든 땅을 순회하며 나무가 있는 땅이라면, 나무들을 모두 체크하여 나이가 5의 배수인 나무들의 8-adjacent에 나이 1 짜리 나무를 넣어준다.
나무는 나이가 어린 순으로 양분을 먹어야 하기 때문에 편의상 새로 생기는 나무들은 deque의 맨 앞에 넣어준다.
-
겨울
void winter(){ for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ energy[i][j] += s2d2[i][j]; } } }겨울에는 s2d2가 전체 땅에 양분을 공급한다. energy 배열에 더해줌으로써 쉽게 구현 가능하다.
전체 나무의 개수는 totalTree 변수로 관리하고, 나무가 번식할 때 더해주고 죽을 때 빼준다.
런타임 에러가 발생하여 한참을 고생했는데, list의 erase를 사용할 때 발생한 문제였다.
for(auto &x: list<int> L)
다음과 같이 리스트를 순회할 때는 리스트에 변화가 생기면 안된다.
변화가 생기면 런타임 에러가 발생하게 된다.
전체 코드는 다음과 같다.
#include <iostream>
#include <deque>
#include <list>
using namespace std;
struct soil{
int tree_num;
deque<int> forest;
};
int N,M,K;
struct soil ground[11][11];
bool isTree[11][11];
int energy[11][11];
int s2d2[11][11];
int deadEnergy[11][11];
int totalTree;
int y_iter[8] = {-1,-1,-1,0,0,1,1,1};
int x_iter[8] = {-1,0,1,-1,1,-1,0,1};
void printTree(){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
cout << ground[i][j].tree_num << " ";
}
cout << endl;
}
// cout << endl;
// for(int i=1;i<=N;i++){
// for(int j=1;j<=N;j++){
// cout << energy[i][j] << " ";
// }
// cout << endl;
// }
}
void spring(){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(ground[i][j].tree_num > 0){
deque<int>::iterator tmp = ground[i][j].forest.begin();
for(auto& x:ground[i][j].forest){
energy[i][j] -= x;
if(energy[i][j] < 0){
energy[i][j] += x;
break;
}
x++;
tmp++;
}
while(tmp != ground[i][j].forest.end()){
totalTree--;
ground[i][j].tree_num--;
deadEnergy[i][j] += *tmp / 2;
tmp = ground[i][j].forest.erase(tmp);
}
}
}
}
}
void summer(){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
energy[i][j] += deadEnergy[i][j];
deadEnergy[i][j] = 0;
}
}
}
void fall(){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(ground[i][j].tree_num > 0){
for(auto &x:ground[i][j].forest){
if(x%5==0){
for(int k=0;k<8;k++){
int temp_y = i+y_iter[k];
int temp_x = j+x_iter[k];
if(temp_y>0 && temp_x >0 && temp_y <= N && temp_x <=N){
ground[temp_y][temp_x].forest.push_front(1);
totalTree++;
ground[temp_y][temp_x].tree_num++;
}
}
}
}
}
}
}
}
void winter(){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
energy[i][j] += s2d2[i][j];
}
}
}
int main(){
cin >> N >> M >> K;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
cin >> s2d2[i][j];
energy[i][j] = 5;
ground[i][j].tree_num = 0;
}
}
totalTree = M;
for(int i=0;i<M;i++){
int x,y,z;
cin >> y >> x >> z;
isTree[y][x] = true;
ground[y][x].tree_num++;
ground[y][x].forest.push_front(z);
}
//simulate
for(int year = 0;year<K;year++){
// cout << year << endl;
// printTree();
spring();
summer();
fall();
winter();
// printTree();
// cout << totalTree << endl;
}
cout << totalTree << endl;
}
댓글남기기