백준 16235 나무 재테크 C++ 풀이 - 시뮬레이션

단순 구현 문제다.

문제에 주어진 대로 구현만 하면 무난하게 풀 수 있는 구현 능력 테스트 문제인 것 같다.

 

구현 문제의 접근 방식은 딱히 없다.

그냥 주어진 조건을 어떻게 하면 컴퓨터적으로 받아들여 저장하고 갱신할 수 있을지만 생각하며 된다.

 

조금 주의해야할 점은

1. 초기에 양분은 모두 5이다.

2. 나무가 같은 땅에 여러 그루 있을 수 있다.

3. 여러 그루 있을 시 어린 나무부터 양분을 흡수한다.

4. 죽은 나무를 바로 양분으로 바꿔버리면 원래 죽어야할 나무가 양분을 흡수하는 경우가 생길 수 있다.

 

해결 못했었던 문제는 다음과 같다.

1. 시간 초과 - 47%? 정도에서 시간 초과가 지속적으로 났다. 이는 어린 나무부터 양분을 흡수하는 것을 구현하기 위해 priority queue를 선택했었는데, pq에 넣고 빼는 것이 상당한 시간을 소요하기 때문에 벌어진 일로 보인다.

 

위 문제를 해결한 방식은 다음과 같다.

1. algorithm 을 include 하여 vector를 sort함수로 정렬해서 풀었다. 확실히 시간 차이가 난다.

 

전체코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>


#define MAX_N 10

using namespace std;

int dy[] = { -1,-1,-1,0,0,1,1,1 };
int dx[] = { -1,0,1,-1,1,-1,0 ,1};
vector <int> tree[MAX_N+1][MAX_N+1]; //나무 저장
int A[MAX_N+1][MAX_N+1]; //로봇이 주는 양분
int map[MAX_N + 1][MAX_N + 1]; //현재 양분

int n, m, k;



void inputData() {

	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]);
			map[i][j] = 5;
		}
	}

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

}
void SpringSummer() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			//어린 나무부터 양분 먹기
			sort(tree[i][j].begin(), tree[i][j].end());
			int flag = 0;
			for (int num = 0; num < tree[i][j].size(); num++) {
				//양분 먹을 수 있는 경우
				if (map[i][j] >= tree[i][j][num] && !flag) {
					map[i][j] -= tree[i][j][num];
					tree[i][j][num]++;
				}
				else {
                //양분 먹을 수 없는 나이부터 뒤에 있는 나무들은 전부 죽을 수 밖에 없다.
					flag = 1;
					map[i][j] += tree[i][j][num] / 2;//양분
					tree[i][j].erase(tree[i][j].begin() + num);//나무 삭제
					num--; //벡터 하나 지웠기 때문에 index 제자리
					m--;//총 나무 수
				}
			}
		}
	}
}

void FallWinter() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int num = 0; num < tree[i][j].size(); num++) {
            //5의 배수일 때
				if (tree[i][j][num]% 5 == 0) {
                //8방향으로 번식
					for (int k = 0; k < 8; k++) {
						int ny = i + dy[k];
						int nx = j + dx[k];
						if (ny > n || ny <= 0 || nx > n || nx <= 0) continue;
						tree[ny][nx].push_back(1);
						m++;//나무 수 증가
					}
				}
			}
			map[i][j] += A[i][j];//겨울, 로봇이 양분줌
		}
	}
}

int solve() {
	for (int year = 0; year < k; year++) {
		SpringSummer();
		if (m == 0) return 0;//나무가 한 그루도 없다면 더 진행할 필요 없이 종료
		FallWinter();
	}
	return m;
}

int main() {
	inputData();
	printf("%d\n", solve());
}