[코드트리] 바이러스 실험

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/virus-experiment/description?page=1&pageSize=20

💻 문제 풀이 : C++

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

using namespace std;

int N, M, K;
int MAP[15][15];
int Feed[15][15];

int dr[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
int dc[] = { -1, 1, 0, 0, 1, -1, 1, -1 };

struct Virus {
	int row, col, age;
};

vector<Virus> virus;
vector<Virus> newVirus;
vector<Virus> deadVirus;
vector<Virus> breedVirus;

bool cmp(Virus a, Virus b)
{
	if (a.age < b.age) return true;
	if (a.age > b.age) return false;
	return false;
}

void getGrow()
{
	int virusSize = virus.size();
	for (int i = 0; i < virusSize; i++)
	{
		int row = virus[i].row;
		int col = virus[i].col;
		int age = virus[i].age;

		if (age <= MAP[row][col])
		{
			// 양분 섭취
			MAP[row][col] -= age;
			// 나이 1 증가
			newVirus.push_back({ row, col, age + 1 });
			// 나이가 5의 배수이면
			if ((virus[i].age + 1) % 5 == 0)
				breedVirus.push_back(virus[i]);
		}
		else
		{
			// 섭취할 수 없다면 죽음
			deadVirus.push_back({ row, col, age / 2 });
		}
	}
}

void getBreed()
{
	for (int i = 0; i < breedVirus.size(); i++)
	{
		for (int dir = 0; dir < 8; dir++)
		{
			int nr = breedVirus[i].row + dr[dir];
			int nc = breedVirus[i].col + dc[dir];
			if (nr <= 0 || nc <= 0 || nr > N || nc > N) continue;
			newVirus.push_back({ nr, nc, 1 });
		}
	}
}

void getFeed(int Array[15][15])
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			MAP[i][j] += Array[i][j];
		}
	}
}

void CLEAR()
{
	virus.clear();
	memset(MAP, 0, sizeof(MAP));
	memset(Feed, 0, sizeof(Feed));
}

void INPUT()
{
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> Feed[i][j];
			MAP[i][j] = 5;
		}
	}
	for (int i = 0; i < M; i++)
	{
		int r, c, age;
		cin >> r >> c >> age;
		virus.push_back({ r, c, age });
	}
}

void SOLVE()
{
	int t = 0;
	while (t < K)
	{
		newVirus.clear();
		breedVirus.clear();
		deadVirus.clear();
		// 1. 나이가 어린 바이러스부터 양분을 섭취
		sort(virus.begin(), virus.end(), cmp);
		getGrow();
		// 2. 섭취가 끝나면 양분으로 변함
		for (int s = 0; s < deadVirus.size(); s++)
			MAP[deadVirus[s].row][deadVirus[s].col] += deadVirus[s].age;
		// 3. 번식 진행
		getBreed();
		// 4. 양분을 추가
		getFeed(Feed);
		virus = newVirus;
		t++;
	}

	cout << virus.size() << endl;
}

int main()
{
	CLEAR();
	INPUT();
	SOLVE();

	return 0;
}

---

📌 memo 😊

⭐ 시간초과 발생
=> Erase를 하면 시간이 급격히 늘어나는듯...?

• 구현에서는 배열의 삽입,삭제는 최소화해야
• 복사는 오히려 괜찮은듯
• 왜지...?!

sort는 상관 X