[백준 16235] 나무 재테크

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

16235번: 나무 재테크

#include <cstdio>
#include <vector>
#include <algorithm>
int N, M, K;	
int F[10 + 2][10 + 2];	// 각 칸에 남아있는 양분 
int A[10 + 2][10 + 2];	// 겨울에 추가할 양분


struct _dt
{
	int x;
	int y;
	int age;
};

std::vector<int> Field[10 + 2][10 + 2];
std::vector<int> Alive[10 + 2][10 + 2];		// 산 나무 정보 저장
std::vector<_dt> Dead;	// 죽은 나무 정보 저장


void input()
{
	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]);
			F[i][j] = 5;	// 가장 처음에 양분은 모든 칸에 5만큼 들어있다.
		}
	}
	for (int i = 0; i < M; i++) {
		int x = 0, y = 0, z = 0;
		scanf("%d %d %d", &x, &y, &z);
		Field[x][y].push_back(z);
	}
}


void give_food(int x, int y, int size)
{
	for (int i = 0; i < size; i++) {
		int nage = Field[x][y][i];
		int nfood = F[x][y];
		if (nfood < nage) {	// 땅의 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없다면 
			Dead.push_back({ x, y, nage });	// 즉시 죽음 
			continue;
		}
		F[x][y] -= nage;
		nage += 1;
		Alive[x][y].push_back(nage);
	}
}




void spring()
{
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int f_size = Field[i][j].size();
			if (f_size == 0) continue;
			std::sort(Field[i][j].begin(), Field[i][j].end());
			give_food(i, j, f_size);
		}
	}
	
	// 다음 계절 및 년도를 위해 산 나무를 Field에 저장한다. 
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			Field[i][j].clear();
			int a_size = Alive[i][j].size();
			for (int k = 0; k < a_size; k++) {
				Field[i][j].push_back( Alive[i][j][k] );
			}
			Alive[i][j].clear();
		}
	}
}


void summer()
{
	int d_size = Dead.size();
	for (int i = 0; i < d_size; i++) {
		int nx = Dead[i].x;
		int ny = Dead[i].y;
		F[nx][ny] += Dead[i].age / 2;	// 죽은 나무의 나이 / 2 값이 나무가 있던 칸에 양분으로 추가
	}
	Dead.clear();
}



void breed(int x, int y, int size)
{
	static int dir_x[8] = { 0, 0, 1, 1, 1, -1, -1, -1 };
	static int dir_y[8] = { 1, -1, 0, 1, -1, 0, 1, -1 };
	
	for (int i = 0; i < size; i++) {
		if (Field[x][y][i] % 5 == 0) {
			for (int p = 0; p < 8; p++) {
				int nx = x + dir_x[p];
				int ny = y + dir_y[p];

				if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
				Field[nx][ny].push_back({ 1 });
			}
		}
	}
}



void fall()
{
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int f_size = Field[i][j].size();
			breed(i, j, f_size);
		}
	}
}



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



void simul()
{
	for (int y = 0; y < K; y++) {
		spring();
		summer();
		fall();
		winter();
	}
}




int output()
{
	int total = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			total += Field[i][j].size();	// 땅에 남아있는 나무 개수 누적 
		}
	}
	return total;
}


int main()
{
	input();
	simul();
	int ans = output();
	printf("%d\n", ans);
	return 0;
}

아니 나 미쳤어? 왜 풀려? 대박이다 나>//<

 

 

// input( ) 함수

겨울에 추가될 양분이 저장되는 배열인 A를 입력받으면서, F 배열의 초기값을 5로 설정해주었다. 문제에서 '가장 처음에 양분은 모든 칸에 5만큼 들어있다'고 했기 때문이다. 

int를 원소로 갖는 이차원 벡터 Field를 생성하고, 각 Field[x][y] 칸에는 해당 좌표에 서식하는 나무의 나이를 저장해주었다. 

 

 

// simul( ) 함수

K년이 지난 후 사계절을 지나면서 살아남은 나무의 개수를 구하기 위해 루프를 돌린다. 

각 계절 동안 해야할 일을 함수로 구현해주었다. 

 

1. spring( ) 함수

루프를 돌면서 각 칸에 서식하는 나무가 존재한다면(Field[i][j].size() != 0) 자신의 나이만큼 양분을 먹고 한 살 증가시키기 위해 give_food( ) 함수를 호출한다. 

이때 나이가 어린 나무부터 양분을 먹어야 하므로 벡터를 정렬해준다. 

해당 칸에 서식하는 나무를 하나씩 확인하면서, 만약 땅에 남아있는 양분이 나무의 양분보다 적다면 즉시 죽는다. 이렇게 죽은 나무는 여름철에 다시 그 칸의 양분이 될 수 있으므로 Dead라는 벡터에 따로 저장해준다. 

한편 땅에 남아있는 양분이 나무의 양분보다 많다면, 나무의 나이만큼 양분을 먹어야 하므로 F[x][y] -= nage를 하고, 나무의 나이를 1 증가시킨다. 이렇게 살아남은 나무는 Alive라는 벡터에 따로 저장해준다. 

 

모든 칸에 서식하는 나무를 확인하면서 양분을 먹고 나이를 증가시키는 과정이 끝났다면, 다음 계절 및 내년을 위해 Alive 배열에 저장해 놓았던 나무의 나이 정보들을 Field로 옮겨준다. 

다음 연산을 진행할 때 이전의 정보가 남아있으면 안되므로, 루프를 돌리면서 각 벡터를 반드시 초기화해준다. 

 

2. summer( ) 함수

여름에는 봄에 죽은 나무가 양분으로 변하게 된다. 따라서 죽은 나무를 따로 저장한 Dead 벡터를 탐색하면서 (nx, ny) 위치에서 죽은 나무의 나이를 2로 나누어 해당 칸의 양분정보를 F[nx][ny]에 누적시켜준다.

 

3. fall( ) 함수

가을에는 나무가 번식한다. 이를 위해 루프를 돌면서 해당 칸에 나무가 존재하면, 그 나무가 번식을 할 수 있는지 없는지 판별하기 위해 breed( ) 함수를 호출한다.

만약 해당 칸에 서식하는 나무의 나이가 5의 배수라면(Field[x][y][i] % 5 == 0) 인접한 8개의 칸 중 영역을 벗어나지 않은 곳에 나이가 1인 나무를 번식시킨다. 

 

 4. winter( ) 함수

겨울에는 각 칸에 양분을 추가시킨다. 모든 칸을 돌면서 기존에 남아있던 양분 F[i][j]에 A[i][j]를 추가한다. 

 

 

// output( ) 함수

K년이 지난 후 살아남은 나무의 개수를 파악해야 하기 때문에, 벡터 Field를 돌면서 각 칸에 몇 개의 나무가 남아있는지 확인하여 누적한다. 

 

---

++ 22.12.05 무수한 실패끝에 갱신..

우선순위 큐로 깔끔하게 컷하려고 했는데 내가 컷당함... 우선순위 큐 쓰면 시간초과 난다.

벡터 + 정렬 써야한다. 

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
int N, M, K;
int Ground[10 + 2][10 + 2];
int A[10 + 2][10 + 2];


struct _st
{
	int x, y;
	int age;
};

std::vector<int> Tree[10 + 2][10 + 2];
std::vector<int> TMP[10 + 2][10 + 2];
std::queue<_st> Dead;



void input()
{
	scanf("%d %d %d", &N, &M, &K);
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			scanf("%d", &A[r][c]);
		}
	}

	for (int i = 1; i <= M; i++) {
		int x = 0, y = 0, z = 0;
		scanf("%d %d %d", &x, &y, &z);
		Tree[x][y].push_back(z);
	}

	// 초기 양분 5
	std::fill(&Ground[0][0], &Ground[0][0] + sizeof(Ground) / sizeof(int), 5);
}


void spring()
{
	// init
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			TMP[r][c].clear();
			std::sort(Tree[r][c].begin(), Tree[r][c].end());
		}
	}

	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			if (Tree[r][c].empty()) continue;

			for (int age : Tree[r][c]) {
				if (age > Ground[r][c]) Dead.push({ r, c, age });
				else {
					Ground[r][c] -= age;
					TMP[r][c].push_back(age + 1);
				}
			}
			Tree[r][c].clear();
		}
	}
}


void summer()
{
	while (!Dead.empty()) {
		_st data = Dead.front();
		Dead.pop();

		int nut = data.age / 2;
		Ground[data.x][data.y] += nut;
	}
}


void fall()
{
	// dir
	int dir_x[8] = { 0, 0, 1, 1, 1, -1, -1, -1 };
	int dir_y[8] = { -1, 1, 0, -1, 1, 0, -1, 1 };

	// init
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			Tree[r][c].clear();
			std::sort(TMP[r][c].begin(), TMP[r][c].end());
		}
	}

	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			if (TMP[r][c].empty()) continue;

			for (int age : TMP[r][c]) {
				if (age % 5 == 0) {
					for (int p = 0; p < 8; p++) {
						int nr = r + dir_x[p];
						int nc = c + dir_y[p];
						if (nr < 1 || nr > N || nc < 1 || nc > N) continue;
						Tree[nr][nc].push_back(1);
					}
					Tree[r][c].push_back(age);
				}
				else Tree[r][c].push_back(age);
			}
			TMP[r][c].clear();
		}
	}
}

void winter()
{
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			Ground[r][c] += A[r][c];
		}
	}
}


void simulation()
{
	for (int k = 1; k <= K; k++) {
		spring();
		summer();
		fall();
		winter();
	}
}


int  output()
{
	int total = 0;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			total += Tree[r][c].size();
		}
	}
	return total;
}


int main()
{
	input();
	simulation();
	printf("%d\n", output());
	return 0;
}