[BOJ] 16235 나무 재테크

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

16235번: 나무 재테크

 

비교적 쉬운 문제였지만 (문제 설명대로 구현만 하면 됐기에)

시간 제한이 0.3초로 매우 짧았기때문에 처음 제출한 코드는 시간초과가 떴다.

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, K;
int A[20][20]; // 로봇이 공급하는 양분
int nutrient[20][20];

struct TREE {
	int age, isDead;
};

vector <TREE> MAP[20][20];

int di[] = { -1,-1,-1,0,1,1,1,0 };
int dj[] = { -1,0,1,1,1,0,-1,-1 };

void input()
{
	int x, y, z;
	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]);
			nutrient[i][j] = 5; // 양분 초기값 = 5
		}
	}

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

void print_MAP()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (MAP[i][j].size())
			{
				for (int k = 0; k < MAP[i][j].size(); k++)
				{
					//printf("MAP[%d][%d] >> %d번 나무의 age = %d\n", i, j, k, MAP[i][j][k].age);
				}
			}
		}
	}
}

bool cmp(TREE t1, TREE t2)
{
	return t1.age < t2.age;
}

void spring()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int numTree = MAP[i][j].size();
			if (numTree > 0)
			{
				// sort 확인
				sort(MAP[i][j].begin(), MAP[i][j].end(), cmp);
				/*
				for (int k = 0; k < MAP[i][j].size(); k++)
				{
					printf("MAP[%d][%d] >> %d번 나무의 age = %d, isDead = %d\n", i, j, k, MAP[i][j][k].age, MAP[i][j][k].isDead);
				}
				*/

				for (int k = 0; k < numTree; k++)
				{
					if (MAP[i][j][k].age <= nutrient[i][j] && MAP[i][j][k].isDead == 0)
					{
						nutrient[i][j] -= MAP[i][j][k].age;
						MAP[i][j][k].age += 1;
						//printf("> MAP[%d][%d][%d].age ==> %d\n> nutrient[%d][%d] = %d\n", i, j, k, MAP[i][j][k].age, i, j, nutrient[i][j]);
					}
					else
					{
						// 죽는 나무 표시
						MAP[i][j][k].isDead = 1;
					}
				}
			}
		}
	}
}

void summer()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int numTree = MAP[i][j].size();
			if (numTree > 0)
			{
				for (int k = 0; k < numTree; k++)
				{
					if (MAP[i][j][k].isDead == 1)
					{
						nutrient[i][j] += MAP[i][j][k].age / 2;
					}
				}
			}
		}
	}
}

void autumn()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int numTree = MAP[i][j].size();
			if (numTree > 0)
			{
				for (int k = 0; k < numTree; k++)
				{
					if (MAP[i][j][k].age % 5 == 0 && MAP[i][j][k].isDead == 0)
					{
						for (int m = 0; m < 8; m++)
						{
							int ni = i + di[m];
							int nj = j + dj[m];

							if (ni <= 0 || ni > N || nj <= 0 || nj > N) continue;
							TREE newtree = { 1, 0 }; // age: 1, isDead: 0
							MAP[ni][nj].push_back(newtree);
						}
					}
				}
			}
		}
	}
}

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

int countTrees()
{
	int cnt = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int numTree = MAP[i][j].size();
			if (numTree > 0)
			{
				for (int k = 0; k < numTree; k++)
				{
					if (MAP[i][j][k].isDead == 0)
					{
						cnt++;
					}
				}
			}
		}
	}
	return cnt;
}

int solve()
{
	int sol = 0;

	while (K--)
	{
		spring();
		summer();
		autumn();
		winter();
	}

	sol = countTrees();
	return sol;
}

int main(void)
{
	input();
	int answer = solve();
	printf("%d\n", answer);
	return 0;
}

시간초과 난 코드

 

질문글에 찾아보니 sort( ) 함수 사용 시, 내가 만든 cmp 함수를 인자로 넣으면 시간 초과가 발생한다고 했다.

그렇지만 난 TREE라는 구조체 안에 나무의 나이와 생존 여부를 넣어줬기 때문에 cmp 함수를 꼭 써야하는 상황이었다.

 

다른 방법으로 시간을 단축시킬 방법을 찾아봤는데, deque 자료구조를 사용하여 정렬 횟수를 줄이는 방법이 있었다.

deque 자료구조는 front와 back에서 각각 push/pop 연산을 수행할 수 있으므로

spring( ) 함수 실행 시, 정렬을 해주지 않아도 됐다.

 

#include <stdio.h>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int N, M, K;
int A[20][20]; // 로봇이 공급하는 양분
int nutrient[20][20];

deque <int> MAP[20][20];
vector <int> deadTree[20][20];

int di[] = { -1,-1,-1,0,1,1,1,0 };
int dj[] = { -1,0,1,1,1,0,-1,-1 };

void input()
{
	int x, y, z;
	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]);
		}
	}

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

void initialize()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			nutrient[i][j] = 5; // 양분 초기값 = 5
			int numTree = MAP[i][j].size();
			if (numTree > 0)
			{
				sort(MAP[i][j].begin(), MAP[i][j].end());
			}
		}
	}
}

void spring()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int numTree = MAP[i][j].size();
			if(numTree > 0)
			{
				while (numTree --)
				{
					// 오름차순 정렬되어있는 상태임
					int age = MAP[i][j].front();
					if (age <= nutrient[i][j])
					{
						nutrient[i][j] -= age;
						MAP[i][j].push_back(age + 1);
						//printf("MAP[%d][%d].push_back(%d)\n", i, j, age + 1);
					}
					else
					{
						deadTree[i][j].push_back(age);
						//printf("deadTree[%d][%d].push_back(%d)\n", i, j, age);
					}
					MAP[i][j].pop_front(); // 항상 오름차순을 유지할수 있도록 pop_front()
				}
			}
		}
	}
}

void summer()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int numDeadTree = deadTree[i][j].size();
			if (numDeadTree > 0)
			{
				for (int k = 0; k < numDeadTree; k++)
				{
					int age = deadTree[i][j][k];
					nutrient[i][j] += (age / 2);
				}

				deadTree[i][j].clear();
			}
		}
	}
}

void autumn()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int numTree = MAP[i][j].size();
			if (numTree > 0)
			{
				for (int k = 0; k < numTree; k++)
				{
					if (MAP[i][j][k] % 5 == 0)
					{
						for (int m = 0; m < 8; m++)
						{
							int ni = i + di[m];
							int nj = j + dj[m];

							if (ni <= 0 || ni > N || nj <= 0 || nj > N) continue;
							MAP[ni][nj].push_front(1);
							//printf("MAP[%d][%d].push_front(%d)\n", ni, nj, 1);
						}
					}
				}
			}
		}
	}
}

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

int countTrees()
{
	int cnt = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int numTree = MAP[i][j].size();
			if (numTree > 0)
			{
				cnt += numTree;
			}
		}
	}
	return cnt;
}

int solve()
{
	int sol = 0;

	while (K--)
	{
		spring();
		summer();
		autumn();
		winter();
	}

	sol = countTrees();
	return sol;
}

int main(void)
{
	input();
	initialize();
	int answer = solve();
	printf("%d\n", answer);
	return 0;
}

정답 코드