16235 - 나무 재태크
나무 키우기를 갔다가 시뮬레이션 하여 K 년 후에 남아있는 나무의 수를 구하는 문제입니다.
다음과 같은 사계절을 지나면 1년이 완성됩니다.
1. 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
2. 여름에는 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
3. 가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 문제에 주어진 땅을 벗어나는 칸에는 나무가 생기지 않는다.
4. 겨울에는 로봇이 땅을 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.
source : https://www.acmicpc.net/problem/16235
얼핏 보면 그냥 시뮬레이션 해 구하면 될 것 같지만 나무의 수가 '가을' 단계에 의해 엄청나게 증가하고, 또 시간 제한이 0.3초라는 점을 감안하면 더 좋은 방법이 필요하다는 것을 알 수 있습니다.
다음과 같은 배열을 생각해봅시다.
10*10의 배열이 있고, 각각의 칸은 deque를 나타냅니다. 이 deque들을은 오름차순이 되게 값을 넣어줄 것입니다. 이점을 생각해서 각각의 단계를 구현해봅시다.
Spring & Summer
(편의상 봄과 여름은 하나의 함수로 구현하였습니다)
배열은 오름차순이므로 앞에서 부터 맨 앞에 있는 item을 구하고 그 값은 일단 pop을 해줍니다. 그리고 얻은 나의와 현재 그 칸의 양분양과 비교하여 다음과 같은 연산을 수행해줍니다.
-양분이 충분하다 : 나이를 1증가하고 deque의 반대편에 넣어줍니다. 양분에서 얻은 나의만큼 빼줍니다.
-양분이 부족하다 : 그 뒤로는 전부 죽을 것이므로(오름차순 정렬) /2한 값을 양분에 더하고 배열에서 빼줍니다. 그 뒤에 값들은 이 연산을 수행 안하고 바로 /2해서 양분에 더해주고 배열에서 빼줍니다.
구현은 다음과 같습니다.
void springAndSummer() {
for(int i = 0;i<n;++i) {
for(int j = 0;j<n;++j) {
bool KILLALL = false;
int queueSize = forest[i][j].size();
for(int idx = 0;idx<queueSize;++idx) {
int curItem = forest[i][j].front();
forest[i][j].pop_front();
if(!KILLALL && nutrients[i][j] < curItem) {
KILLALL = true;
}
if(KILLALL) {
nutrients[i][j] += curItem/2;
aliveTrees--;
} else {
forest[i][j].push_back(curItem+1);
nutrients[i][j] -= curItem;
}
}
}
}
}
Autumn
우선 나의가 5의 배수인지 체크해줍니다. 그 후 5의 배수이면 그 칸에서 8방향을 체크해 주어 범위 안에 있는 칸들은 그 칸의 deque 앞에 1을 추가해줍니다.
구현은 다음과 같습니다.
int ni[8] = {-1, -1, -1, 0,0,1,1,1};
int nj[8] = {-1, 0, 1, -1, 1, -1, 0,1};
bool isIn(int i, int j) {
if(i < 0 || j < 0 || i >= n || j >= n) {
return false;
}
return true;
}
void autumn() {
for(int i = 0;i<n;++i) {
for(int j = 0;j<n;++j) {
int queueSize = forest[i][j].size();
for(int idx = 0;idx<queueSize;++idx) {
int curItem = forest[i][j].front();
forest[i][j].pop_front();
if(curItem %5==0) {
for(int d = 0;d<8;++d) {
int newI = i + ni[d];
int newJ = j + nj[d];
if(isIn(newI, newJ)) {
forest[newI][newJ].push_front(1);
aliveTrees++;
}
}
}
forest[i][j].push_back(curItem);
}
}
}
}
Winter
이건 상대적으로 간단합니다. 그냥 2중 for문을 돌며 미리 저장해둔 값들만큼 더해주면 됩니다.
구현은 다음과 같습니다.
void winter() {
for(int i = 0;i<n;++i) {
for(int j = 0;j<n;++j) {
nutrients[i][j]+=nutrientIncrements[i][j];
}
}
}Total Source Code
전체 소스 코드입니다. 살아있는 나무의 수를 다시 세는 수고를 방지하기 위해 aliveTrees 라는 변수를 관리해주었습니다.
#include <stdio.h>
#include <deque>
#include <vector>
using namespace std;
deque<int> forest[10][10];
int nutrients[10][10];
int nutrientIncrements[10][10];
int n = 0;
int m = 0;
int k = 0;
struct Tree {
int i = 0;
int j = 0;
int age = 1;
};
int ni[8] = {-1, -1, -1, 0,0,1,1,1};
int nj[8] = {-1, 0, 1, -1, 1, -1, 0,1};
int aliveTrees = 0;
bool isIn(int i, int j) {
if(i < 0 || j < 0 || i >= n || j >= n) {
return false;
}
return true;
}
void springAndSummer() {
for(int i = 0;i<n;++i) {
for(int j = 0;j<n;++j) {
bool KILLALL = false;
int queueSize = forest[i][j].size();
for(int idx = 0;idx<queueSize;++idx) {
int curItem = forest[i][j].front();
forest[i][j].pop_front();
if(!KILLALL && nutrients[i][j] < curItem) {
KILLALL = true;
}
if(KILLALL) {
nutrients[i][j] += curItem/2;
aliveTrees--;
} else {
forest[i][j].push_back(curItem+1);
nutrients[i][j] -= curItem;
}
}
}
}
}
void autumn() {
for(int i = 0;i<n;++i) {
for(int j = 0;j<n;++j) {
int queueSize = forest[i][j].size();
for(int idx = 0;idx<queueSize;++idx) {
int curItem = forest[i][j].front();
forest[i][j].pop_front();
if(curItem %5==0) {
for(int d = 0;d<8;++d) {
int newI = i + ni[d];
int newJ = j + nj[d];
if(isIn(newI, newJ)) {
forest[newI][newJ].push_front(1);
aliveTrees++;
}
}
}
forest[i][j].push_back(curItem);
}
}
}
}
void winter() {
for(int i = 0;i<n;++i) {
for(int j = 0;j<n;++j) {
nutrients[i][j]+=nutrientIncrements[i][j];
}
}
}
int main(void) {
scanf("%d %d %d",&n, &m, &k);
aliveTrees = m;
for(int i = 0;i<n;++i) {
for(int j = 0;j<n;++j) {
scanf("%d",&nutrientIncrements[i][j]);
nutrients[i][j] = 5;
}
}
for(int i = 0;i<m;++i) {
int a, b,c;
scanf("%d %d %d",&a, &b, &c);
forest[a-1][b-1].push_back(c);
}
for(int year = 1;year <= k;++year) {
springAndSummer();
autumn();
winter();
}
printf("%d", aliveTrees);
}