https://www.acmicpc.net/problem/16235
시뮬레이션이기 때문에 요구대로 코딩하시면 됩니다.
다른 계절은 구현이 쉽지만, 봄을 살짝 고민해야 됐습니다.
전 우선순위큐를 사용하여 봄을 해결했습니다.
어린 나무를 먼저 먹여야했기때문에 정렬이 필요했고,
꺼내고 판단 후 다시 집어넣는 큐의 역할이 필요했기 때문에 우선순위큐가 제격이었습니다.
한가지 단점은 봄에서 우선순위큐를 꺼내고 바로 다시 집어 넣었다간
큐에서 정렬이되어 k가 많은 애는 절대 꺼내질 수없기 때문에
다 꺼낸 녀석을 다른 큐에 넣고 다시 한꺼번에 집어넣어야하는 번거로움이 있었습니다.
이것을 해결하니 나머지는 알아서 척!척!척! 해결됐습니다.
2차 시도
우선순위큐는 편리하긴 하지만 시간을 많이 잡아먹기 때문에 다른 방법을 사용했습니다.
바로 deque!! deque는 넣고 빼기가 앞뒤 가능하기 때문에 편리할 뿐아니라, deque[3]처럼 배열 쓰듯이 참조할 수 있기때문에
매우매우 편리한 녀석입니다. 이 녀석을 사용하여 문제를 쉽게 해결했습니다.
2차
#include<iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, k, a[11][11], map[11][11];
struct treeInfo {
int x;
int y;
int z;
};
deque <treeInfo> dq;//산 나무 덱
deque <treeInfo> dieTree;//죽은 나무 덱
vector <treeInfo> v;//처음 입력받을 때 어린나무부터 정렬하기위해
int dx[] = { -1,-1,-1,0,1,1,1,0 };
int dy[] = { -1,0,1,1,1,0,-1,-1 };
void winter() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
map[i][j] += a[i][j];
}
}
}
void fall() {
int size = dq.size();
v.clear();
for (int t = 0; t < size; t++) {
if ((dq[t].z) % 5 == 0) {//벡터에서 먼저 넣은 후
for (int i = 0; i < 8; i++) {
int nx = dq[t].x + dx[i];
int ny = dq[t].y + dy[i];
if (nx > 0 && ny > 0 && nx <= n && ny <= n) {
v.push_back({ nx,ny,1 });
}
}
}
}
for (int i = 0; i < v.size(); i++) {//벡터에 받은 애들을 덱에 넣는다
dq.push_front({ v[i].x,v[i].y,v[i].z });//여기선 앞에다 넣는다
}
winter();
}
void summer() {
while (!dieTree.empty()) {
int x = dieTree.front().x;
int y = dieTree.front().y;
int z = dieTree.front().z;
dieTree.pop_front();
map[x][y] += z / 2;
}
fall();
}
void spring() {
int size = dq.size();
for (int t = 0; t < size; t++) {//여기서 덱은 큐처럼 사용
int x = dq.front().x;
int y = dq.front().y;
int z = dq.front().z;
dq.pop_front();
if (map[x][y] >= z) {
map[x][y] -= z;
z += 1;
dq.push_back({ x,y,z });
}
else dieTree.push_back({ x,y,z });
}
summer();
}
bool comp(treeInfo a, treeInfo b) {
return a.z < b.z;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
map[i][j] = 5;
}
}
int x = 0, y = 0, z = 0;
for (int i = 0; i < m; i++) {
cin >> x >> y >> z;
v.push_back({ x,y,z });
}
sort(v.begin(), v.end(), comp);//처음에만 나이에따른 정렬 후
for (int i = 0; i < v.size(); i++) {//덱에 넣는다
dq.push_back({ v[i].x,v[i].y,v[i].z });
}
for (int i = 0; i < k; i++) spring();
cout << dq.size();//덱에 살아있는 나무들 출력
}
1차
#include<iostream>
#include <queue>
using namespace std;
int n, m, k;
int a[11][11];
int map[11][11];
struct TreeInfo {
int x;
int y;
int z;
};
priority_queue <TreeInfo> tree;
queue <TreeInfo> dieTree;
queue <TreeInfo> breedTree;
bool operator<(TreeInfo a, TreeInfo b) {//z에 따른 정렬위해(z 작은놈부터나온다)
return a.z > b.z;
}
void winter() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
map[i][j] += a[i][j];
}
void fall() {
int dx[] = { -1,-1,-1,0,0,1,1,1 };
int dy[] = { -1,0,1,-1,1,-1,0,1 };
while (!breedTree.empty()) {
int x = breedTree.front().x;
int y = breedTree.front().y;
breedTree.pop();
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 1 && ny >= 1 && nx <= n && ny <= n) {
tree.push({ nx,ny,1 });
}
}
}
}
void summer() {
while (!dieTree.empty()) {
int x = dieTree.front().x;
int y = dieTree.front().y;
int z = dieTree.front().z;
dieTree.pop();
map[x][y] += z / 2;
}
}
void spring() {
queue <TreeInfo> q;//q에 잠시 넣었다가 tree우선순위큐에 넣기위해
//(우선순위큐라 아래 반복문을 하면 계속 z가낮은 애만 가져오게 됨
while (!tree.empty()) {
int x = tree.top().x;
int y = tree.top().y;
int z = tree.top().z;
tree.pop();
if (map[x][y] >= z) {//먹을 수 있다면
map[x][y] -= z;
z += 1;
q.push({ x,y,z });
if (z % 5 == 0) breedTree.push({ x,y,z });//5의 배수라면
}
else dieTree.push({ x,y,z });//못 먹어서 죽는다면
}
while (!q.empty()) {//다시 우선순위 큐에 고고
int x = q.front().x;
int y = q.front().y;
int z = q.front().z;
q.pop();
tree.push({ x,y,z });
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
map[i][j] = 5;
}
}
for (int i = 0; i < m; i++) {
int tx, ty, tz;
cin >> tx >> ty >> tz;
tree.push({ tx,ty,tz });//우선순위 큐에 나무 정보 입력
}
for (int i = 0; i < k; i++) {
spring();
summer();
fall();
winter();
}
cout << tree.size();
return 0;
}
- 나 혼자 말하고 나 혼자 듣는 말
우선순위큐 처음 사용했는데 이렇게 좋은걸 이번 기회에 알게돼서 너무 기쁘다.
확실히 익혀서 다음에 또 써야지