[BOJ][백준 16235] 나무 재태크 - C++

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

16235번: 나무 재테크

백준 사이트의 16235번 문제, 나무 재태크 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

• 각각의 칸은 (r, c)로 나타내며, r과 c는 1부터 시작한다.
• 가장 처음에 양분은 모든 칸에 5만큼 들어있다.
• M개의 나무를 구매해 땅에 심었다. 같은 1×1 크기의 칸에 여러 개의 나무가 심어져 있을 수도 있다.
• 입력으로 주어지는 나무의 위치는 모두 서로 다름

이 나무는 사계절을 보내며, 아래와 같은 과정을 반복한다.

나무 재태크 사계절 규칙

• K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하는 프로그램을 작성하시오.

---

1. 문제풀이 아이디어

• 무지막지한 시뮬레이션, 구현 문제이다.
• N과 M이 생각보다 크기 때문에 시간관리에도 신경써야할 것 같다. => 실제로 시간 매우 빡빡
• 최대한 정렬을 최소화 하는 방향으로.
• 근데 어차피 나이 어린게 벡터 뒤로 들어갈거니깐 정렬 필요 없을지도? => 실제로 정렬 필요 없었다.
•  
• 이차원 구조체 벡터로 정보를 저장하자. => 이건 추후에 수정됨, 시간 매우매우매우 잡아먹음.
• 구조체는 나무의 나이와 정보가 들어가면 좋을것 같다.
• 이후에 한번 구현을 갈아엎게 되었다. 이건 추후에 설명하도록 하겠다.
•  
• 각 계절마다 함수를 분리해서 돌리면 될 것 같다.

---

2. 코드 핵심 부분

1) 인자들을 어떻게 받는 부분이 핵심인 문제이다.

   다양한 정보를 처리해야 하는 구현문제, 거기에다가 시간이 빡빡하므로

   어떤 변수, 어떤 정보를 어떤 식으로 저장할지 잘 선택해야한다.

 

   본인은 처음에는 Age를 구조체 벡터로 받고, 구조체 정보에 Alive변수로 살아있는지를 파악했는데

   이 방식은 시간 초과가 나게된다. (죽은 나무도 모두 들고다니게 되므로)

   차라리 죽은 나무를 따로 벡터에 담아서 이걸 처리하는것이 erase를 사용하더라도 시간이 훨씬 단축되었다.

// 정보를 어떻게 저장하는지가 핵심이다.
struct Tree {
	int y;
	int x;
	int age;
};

// 필요 인자들
int N, M, K; // 땅크기, 나무개수, 몇 년
int SD[10][10]; // 로봇이 겨울마다 뿌리는 양분
int Yang[10][10]; // 현재 땅의 양분 정보
int Breeding[10][10]; // 이거도 번식가능 나무 체크하기 위함.
vector<int> Age[10][10]; // 살아있는 나무지도 (0부터로 조정)
vector<Tree> Dead; // 봄에 죽은 나무만 저장함
int Ans; // 살아있는 나무개수

// 방향배열 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1)
int Diry[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int Dirx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

 

2) 봄 함수,

   코드를 보면 정렬이 필요없다는 것을 알 수 있다. (어차피 어린나무가 뒤로 들어가는 구조 + 처음에 칸에 중복없음)

   양분보다 나이가 많으면 "erase"하고 Dead벡터에 넣어줬음.

      => 보통 erase는 시간이 많이 걸려서 사용하지 않는데,

            이 경우에는 erase하는 벡터의 전체길이가 작으므로 오히려 시간이 단축되는 효과를 낳는다.

            (erase의 시간복잡도는 O(n))

// 봄, 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 
// 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
// 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
void spring() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int Size = Age[i][j].size();
			if (!Size) continue;

			// 뒤에부터 확인한다. (그래야 어린 나무부터)
			for (int k = Size - 1; k >= 0; k--) {
				// 양분보다 나이가 많으면 죽음대기 상태로
				if (Age[i][j][k] > Yang[i][j]) {
					Dead.push_back({ i, j, Age[i][j][k] });
					Age[i][j].erase(Age[i][j].begin() + k);
					Ans--;
				}
				// 아니면 양분 먹고 나이 +1
				else {
					Yang[i][j] -= Age[i][j][k];
					Age[i][j][k]++;
					// 5의 배수인지 체크
					if (Age[i][j][k] % 5 == 0)
						Breeding[i][j]++;
				}
			}
		}
	}
}

 

3) 여름 함수,

   봄 함수에서 채워뒀던 Dead 벡터를 처리해준다.

   딱 그 벡터만 보면 되므로 여기서 시간 단축이 많이되었다.

   전부 비워주고 초기화까지

// 여름, 봄에 죽은 나무가 양분으로 변하게 된다. 
// 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다.
void summer() {
	int Size = Dead.size();

	// 양분 추가
	for (int k = 0; k < Size; k++) {
		Yang[Dead[k].y][Dead[k].x] += Dead[k].age / 2;
	}

	// 다 상태 바꿔주고 나서는 Dead 초기화
	Dead.clear();
	Dead.resize(0);
}

 

4) 가을 함수,

   벡터를 하나하나 다 뜯어보면 너무 오래걸리므로,

   breeding이라는 배열을 만들어서 spring함수에서 5의배수 나무가 있는 칸을 체크해놓았다.

   그 칸만 체크해주면 되므로 시간 단축 가능.

// 가을, 가을에는 나무가 번식한다.
// 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
void fall() {
	// Age가 5의 배수인 나무들 체크
	// 근데 이거도 하나하나 체크하기 너무 오래걸리니깐 배열 하나 만들자.
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			// Breeding에 있는 칸만 체크
			if (!Breeding[i][j]) continue;
			int Size = Age[i][j].size();

			// 5의 배수인거 찾아서 주변 8칸 번식.
			for (int k = 0; k < Size; k++) {
				if (Age[i][j][k] % 5 == 0) {
					
					for (int dir = 0; dir < 8; dir++) {

						int ny = i + Diry[dir];
						int nx = j + Dirx[dir];

						if (ny < 0 || nx < 0 || ny >= N || nx >= N)
							continue;

						Age[ny][nx].push_back(1);
						Ans++;
					}
				}
			}

			// 다 상태 바꿔주고 나서는 Breeding 초기화
			Breeding[i][j] = 0;
		}
	}
}

---

3. 전체 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

/*
1. 문제읽기
각각의 칸은 (r, c)로 나타내며, r과 c는 1부터 시작한다.
가장 처음에 양분은 모든 칸에 5만큼 들어있다.
M개의 나무를 구매해 땅에 심었다. 같은 1×1 크기의 칸에 여러 개의 나무가 심어져 있을 수도 있다.
입력으로 주어지는 나무의 위치는 모두 서로 다름

이 나무는 사계절을 보내며, 아래와 같은 과정을 반복한다.

K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하는 프로그램을 작성하시오.
*/

/*
2. 아이디어
무지막지한 시뮬레이션, 구현 문제이다.
N과 M이 생각보다 크기 때문에 시간관리에도 신경써야할 것 같다.
최대한 정렬을 최소화 하는 방향으로.
근데 어차피 나이 어린게 벡터 뒤로 들어갈거니깐 정렬 필요 없을지도?

이차원 벡터 배열로 정보를 저장하자.
구조체는 나무의 나이와 정보가 들어가면 좋을것 같다.

각 계절마다 함수를 분리해서 돌리면 될 것 같다.
*/

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

// 필요 인자들
int N, M, K; // 땅크기, 나무개수, 몇 년
int SD[10][10]; // 로봇이 겨울마다 뿌리는 양분
int Yang[10][10]; // 현재 땅의 양분 정보
int Breeding[10][10]; // 이거도 번식가능 나무 체크하기 위함.
vector<int> Age[10][10]; // 살아있는 나무지도 (0부터로 조정)
vector<Tree> Dead; // 봄에 죽은 나무만 저장함
int Ans; // 살아있는 나무개수

// 방향배열 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1)
int Diry[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int Dirx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

// 값 입력받는 함수
void input() {
	cin >> N >> M >> K;
	Ans = M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> SD[i][j];
		}
	}
	for (int i = 0; i < M; i++) {
		int y, x, age;
		cin >> y >> x >> age;
		Age[y - 1][x - 1].push_back(age);
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			Yang[i][j] = 5;
		}
	}
}

// 봄, 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 
// 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
// 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
void spring() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int Size = Age[i][j].size();
			if (!Size) continue;

			// 뒤에부터 확인한다. (그래야 어린 나무부터)
			for (int k = Size - 1; k >= 0; k--) {
				// 양분보다 나이가 많으면 죽음대기 상태로
				if (Age[i][j][k] > Yang[i][j]) {
					Dead.push_back({ i, j, Age[i][j][k] });
					Age[i][j].erase(Age[i][j].begin() + k);
					Ans--;
				}
				// 아니면 양분 먹고 나이 +1
				else {
					Yang[i][j] -= Age[i][j][k];
					Age[i][j][k]++;
					// 5의 배수인지 체크
					if (Age[i][j][k] % 5 == 0)
						Breeding[i][j]++;
				}
			}
		}
	}
}

// 여름, 봄에 죽은 나무가 양분으로 변하게 된다. 
// 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다.
void summer() {
	int Size = Dead.size();

	// 양분 추가
	for (int k = 0; k < Size; k++) {
		Yang[Dead[k].y][Dead[k].x] += Dead[k].age / 2;
	}

	// 다 상태 바꿔주고 나서는 Dead 초기화
	Dead.clear();
	Dead.resize(0);
}

// 가을, 가을에는 나무가 번식한다.
// 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
void fall() {
	// Age가 5의 배수인 나무들 체크
	// 근데 이거도 하나하나 체크하기 너무 오래걸리니깐 배열 하나 만들자.
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			// Breeding에 있는 칸만 체크
			if (!Breeding[i][j]) continue;
			int Size = Age[i][j].size();

			// 5의 배수인거 찾아서 주변 8칸 번식.
			for (int k = 0; k < Size; k++) {
				if (Age[i][j][k] % 5 == 0) {
					
					for (int dir = 0; dir < 8; dir++) {

						int ny = i + Diry[dir];
						int nx = j + Dirx[dir];

						if (ny < 0 || nx < 0 || ny >= N || nx >= N)
							continue;

						Age[ny][nx].push_back(1);
						Ans++;
					}
				}
			}

			// 다 상태 바꿔주고 나서는 Breeding 초기화
			Breeding[i][j] = 0;
		}
	}
}

// 겨울, S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다.
void winter() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			Yang[i][j] += SD[i][j];
		}
	}
}

// 메인함수
int main() {

	// input
	input();

	// solve -> 각 계절 함수를 순서대로 K년만큼 실행
	for (int year = 1; year <= K; year++) {
		spring();
		summer();
		fall();
		winter();
	}

	// output
	cout << Ans;

	return 0;
}

---

4. 문제 풀이를 마치며..

채점결과,, 무수한 시간초과의 흔적들

문제 정답비율부터 21퍼센트에 시간제한도 매우 적게 주어졌기에 긴장을 막 해서 집중하고 푼 문제이다.

 

그 만큼 변수설정, 함수설계부터 공들여 진행했고, 나름 이쁘게 코드를 잘 짜고 디버깅까지 하고

첫 제출을 했는데

역시나 시간 초과..

 

막막했는데 같은 반 사람들이 요것저것 조언해주고 가르쳐주신 덕분에 결국 풀어낼 수 있었다.

 

역시 SSAFY 최고!

 

1) 구조체 벡터는 시간이 많이걸리고

2) erase가 시간이 적게 걸릴 수도 있다

요런 점들을 얻어갈 수 있었던 문제였다.