[Algorithm][C++] BOJ 16235 나무 제테크

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

16235번: 나무 재테크

 

풀이 핵심

1. 전형적인 시뮬레이션 문제

2. 봄에 나이가 적은 나무 순으로 양분을 먹는 것을 구현하기 위해 deque, sort 사용 (우선순위 큐 사용 시 push 할 때 마다 정렬을 하므로 사용하면 안됨)

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <deque>
#include <vector>
using namespace std;

int n, m, K;
int map[11][11];
int food[11][11];
deque<int> tree[11][11];
vector<int> dead[11][11];
const int dr[] = { 1,-1,0,0,1,1,-1,-1 };
const int dc[] = { 0,0,1,-1,1,-1,1,-1 };

// 입 력
void InputData() {
	scanf("%d %d %d", &n, &m, &K);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			map[i][j] = 5; // 초기 양분은 5
			scanf("%d", &food[i][j]);
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		tree[x][y].push_back(z);
	}
}

// 봄
void Spring() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			// 나이가 적은 나무부터 양분을 섭취 하기 위해 오름차순 sorting
			sort(tree[i][j].begin(), tree[i][j].end());
			// 현재 공간에 나무 수 만큼 반복
			int size = tree[i][j].size();
			while (size--) {
				int age = tree[i][j].front();
				tree[i][j].pop_front();
				if (map[i][j] < age) { // 양분이 나이보다 적다면 dead에 추가
					dead[i][j].push_back(age);
				}
				else {// 양분을 먹고 tree 가장 끝에 추가
					map[i][j] -= age;
					tree[i][j].push_back(age + 1); // 나이 +1 추가
				}
			}
		}
	}
}

// 여 름
void Summer() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			// 현재 위치에서 죽은 나무 수 만큼 진행
			int size = dead[i][j].size();
			while (size--) {
				int age = dead[i][j].back();
				dead[i][j].pop_back();
				map[i][j] += (age / 2);
			}
		}
	}
}

// 가 을
void Fall() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			// 현재 나무 수 만큼 진행, pop 하지 않고 진행
			for (int k = 0; k < tree[i][j].size(); k++) {
				int age = tree[i][j][k];
				if (age % 5 == 0) { // 나이가 5의 배수라면
					for (int dir = 0; dir < 8; dir++) {
						int nr = i + dr[dir];
						int nc = j + dc[dir];
						if (nr < 1 || nr > n || nc < 1 || nc > n) continue;
						tree[nr][nc].push_front(1); // 정렬 속도를 높이기 위해 큐 앞에 추가
					}
				}
			}
		}
	}
}

// 겨 울
void Winter() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			map[i][j] += food[i][j]; // 로봇이 지나다니며 맵에 양분 추가
		}
	}
}

void Solve() {
	// 봄, 여름, 가을, 겨울 K번 만큼 반복
	for (int i = 0; i < K; i++) {
		Spring();
		Summer();
		Fall();
		Winter();
	}
	// 남아 있는 tree 수 계산
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			sum += tree[i][j].size();
		}
	}
	// 정답 출력
	printf("%d", sum);
}

int main() {
	InputData();
	Solve();
	return 0;
}

 

아쉬운점

1. algorithm 헤더의 sort 함수를 사용 할 때 왜 queue를 sort 하려면 어떻게 해야 할까?