[코드트리] 나무박멸

rhkr9080·2023년 9월 3일
C/C++simulation구현코드트리코테대비
0

코드트리

목록 보기
17/29

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/tree-kill-all/description?page=3&pageSize=20

💻 문제 풀이 : C++

📌 1차 풀이 : 오답 => 제초제의 유효기간인 YEAR를 잘못 설정한 듯 => 이유를 모르겠다...😂 
#include <iostream>
#include <cstring>
#include <algorithm>

#define MAX_MAP 25
#define MAX_TREE 105

using namespace std;

int N, M, K, C;

// 나무
int NOW[MAX_MAP][MAX_MAP];
int NEXT[MAX_MAP][MAX_MAP];
// 살충제 기한
int YEAR[MAX_MAP][MAX_MAP];

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

int answer;

int isTree(int r, int c)
{
	if (NOW[r][c] > 0) return 1;
	else return 0;
}

int inRange(int r, int c)
{
	if (r < 0 || c < 0 || r >= N || c >= N)
		return 0;
	else
		return 1;
}

void grow()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (!isTree(i, j)) continue;
			int cnt = 0;
			// 인접한 네 칸 탐색
			for (int d = 0; d < 4; d++)
			{
				int nr = i + dr[d];
				int nc = j + dc[d];
				if (!inRange(nr, nc)) continue;
				if (NOW[nr][nc] > 1)
				{
					cnt++;
				}
			}
			NOW[i][j] += cnt;
		}
	}
}

void spread()
{
	memset(NEXT, 0, sizeof(NEXT));
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (!isTree(i, j)) continue;
			int cnt = 0;
			// 번식 가능한 칸 개수 세기
			for (int d = 0; d < 4; d++)
			{
				int nr = i + dr[d];
				int nc = j + dc[d];
				if (!inRange(nr, nc)) continue;
				if ((NOW[nr][nc] == 0) &&
					(YEAR[nr][nc] == 0))
					cnt++;
			}
			if (cnt == 0) continue;
			int tmpTree = NOW[i][j] / cnt;
			// 번식하기
			for (int d = 0; d < 4; d++)
			{
				int nr = i + dr[d];
				int nc = j + dc[d];
				if (!inRange(nr, nc)) continue;
				if ((NOW[nr][nc] == 0) &&
					(YEAR[nr][nc] == 0))
					NEXT[nr][nc] += tmpTree;
			}
		}
	}

	// MAP에 반영하기
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			NOW[i][j] += NEXT[i][j];
		}
	}
}

int getDelTree(int r, int c)
{
	int cnt = NOW[r][c];

	// 대각선으로 진행
	for (int d = 4; d < 8; d++)
	{
		int nr = r;
		int nc = c;
		// K 범위 진행
		for (int k = 1; k <= K; k++)
		{
			nr += dr[d];
			nc += dc[d];
			if (!isTree(nr, nc)) break;
			if (NOW[nr][nc] == -1) break;
			if (!inRange(nr, nc)) break;
			cnt += NOW[nr][nc];
		}
	}

	return cnt;
}

void herbicide()
{
	// 가장 많이 박멸되는 칸 찾기
	int r = 0, c = 0, cnt = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (!isTree(i, j)) continue;
			int tmpCnt = getDelTree(i, j);
			if (tmpCnt > cnt)
			{
				r = i;
				c = j;
				cnt = tmpCnt;
			}
		}
	}

	if (cnt == 0) {
		return;
	}

	// 제초제 뿌리기
	YEAR[r][c] = C+1;
	answer += NOW[r][c];
	// 대각선으로 진행
	for (int d = 4; d < 8; d++)
	{
		int nr = r;
		int nc = c;
		// K 범위 진행
		for (int k = 1; k <= K; k++)
		{
			nr += dr[d];
			nc += dc[d];
			if (!inRange(nr, nc)) break;
			if (NOW[nr][nc] == -1) break;
			if (!isTree(nr, nc))
			{
				YEAR[nr][nc] = C+1;
				break;
			}
			YEAR[nr][nc] = C+1;
			answer += NOW[nr][nc];
		}
	}
}

void newyear()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (YEAR[i][j] > 0)
			{
				// 제초제가 있는 곳은 나무 박멸
				NOW[i][j] = 0;
				// 제초제 효과 제거
				YEAR[i][j] -= 1;
			}
		}
	}
}

void CLEAR()
{
	memset(NOW, 0, sizeof(NOW));
	answer = 0;
}

void INPUT()
{
	cin >> N >> M >> K >> C;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> NOW[i][j];
		}
	}
}

void SOLVE()
{
	int time = 1;
	while (time <= M)
	{
		// 나무 성장
		grow();
		// 나무 번식
		spread();
		// 제초제
		herbicide();
		// 제초제 효과 업데이트
		newyear();
		time++;
	}
	cout << answer << endl;
}

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

	return 0;
}

📌 정답풀이

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

#define MAX_MAP 25
#define MAX_TREE 105

using namespace std;

int N, M, K, C;

// 나무
int NOW[MAX_MAP][MAX_MAP];
int NEXT[MAX_MAP][MAX_MAP];
// 살충제 기한
int YEAR[MAX_MAP][MAX_MAP];

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

int answer;

int isTree(int r, int c)
{
	if (NOW[r][c] > 0) return 1;
	else return 0;
}

int inRange(int r, int c)
{
	if (r < 0 || c < 0 || r >= N || c >= N)
		return 0;
	else
		return 1;
}

void grow()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (!isTree(i, j)) continue;
			int cnt = 0;
			// 인접한 네 칸 탐색
			for (int d = 0; d < 4; d++)
			{
				int nr = i + dr[d];
				int nc = j + dc[d];
				if (!inRange(nr, nc)) continue;
				if (isTree(nr, nc))
					cnt++;
			}
			NOW[i][j] += cnt;
		}
	}
}

void spread()
{
	memset(NEXT, 0, sizeof(NEXT));
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (!isTree(i, j)) continue;
			int cnt = 0;
			// 번식 가능한 칸 개수 세기
			for (int d = 0; d < 4; d++)
			{
				int nr = i + dr[d];
				int nc = j + dc[d];
				if (!inRange(nr, nc)) continue;
				if ((NOW[nr][nc] == 0) &&
					(YEAR[nr][nc] == 0))
					cnt++;
			}
			if (cnt == 0) continue;
			int tmpTree = NOW[i][j] / cnt;
			// 번식하기
			for (int d = 0; d < 4; d++)
			{
				int nr = i + dr[d];
				int nc = j + dc[d];
				if (!inRange(nr, nc)) continue;
				if ((NOW[nr][nc] == 0) &&
					(YEAR[nr][nc] == 0))
					NEXT[nr][nc] += tmpTree;
			}
		}
	}

	// MAP에 반영하기
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			NOW[i][j] += NEXT[i][j];
		}
	}
}

int getDelTree(int r, int c)
{
	int cnt = NOW[r][c];

	// 대각선으로 진행
	for (int d = 4; d < 8; d++)
	{
		int nr = r;
		int nc = c;
		// K 범위 진행
		for (int k = 1; k <= K; k++)
		{
			nr += dr[d];
			nc += dc[d];
			if (!isTree(nr, nc)) break;
			if (NOW[nr][nc] == -1) break;
			if (!inRange(nr, nc)) break;
			cnt += NOW[nr][nc];
		}
	}

	return cnt;
}

void herbicide()
{
	// 가장 많이 박멸되는 칸 찾기
	int r = 0, c = 0, cnt = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (!isTree(i, j)) continue;
			int tmpCnt = getDelTree(i, j);
			if (tmpCnt > cnt)
			{
				r = i;
				c = j;
				cnt = tmpCnt;
			}
		}
	}

	if (cnt == 0) {
		return;
	}

	// 제초제 뿌리기
	answer += NOW[r][c];
	YEAR[r][c] = C;
	NOW[r][c] = 0;
	// 대각선으로 진행
	for (int d = 4; d < 8; d++)
	{
		int nr = r;
		int nc = c;
		// K 범위 진행
		for (int k = 1; k <= K; k++)
		{
			nr += dr[d];
			nc += dc[d];
			if (!inRange(nr, nc)) break;
			if (NOW[nr][nc] == -1) break;
			if (!isTree(nr, nc))
			{
				YEAR[nr][nc] = C;
				NOW[nr][nc] = 0;
				break;
			}
			answer += NOW[nr][nc];
			YEAR[nr][nc] = C;
			NOW[nr][nc] = 0;
		}
	}
}

void newyear()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (YEAR[i][j] > 0)
			{
				// 제초제 효과 제거
				YEAR[i][j] -= 1;
			}
		}
	}
}

void CLEAR()
{
	memset(NOW, 0, sizeof(NOW));
	answer = 0;
}

void INPUT()
{
	cin >> N >> M >> K >> C;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> NOW[i][j];
		}
	}
}

void SOLVE()
{
	int time = 1;
	while (time <= M)
	{
		// 나무 성장
		grow();
		// 나무 번식
		spread();
		// 제초제 효과 업데이트
		newyear();
		// 제초제
		herbicide();

		time++;
	}
	cout << answer << endl;
}

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

	return 0;
}

📌 memo 😊
⭐ 눈 앞의 테케에 멀어 논리적으로 못 짰다...
=> "논리"를 기준으로 코드를 작성하고, 안 돌아가면 논리를 다시 점검할 것!
=> 예를 들어, 제초제의 유효기간을 C가 아닌 C+1로 동작하게 했음 (일단 TC는 맞아야 하니까!!)
... 논리적으로 C가 맞으니 C로 설정하고, 안돌아가면 왜 안돌아가는지를 확인할 것
=> 이 문제에서는 제초제를 뿌리고나서 바로 제초제의 유효기간이 "번식 이후"에 동작해야함
타이밍을 위주로 생각했어야 하는듯!

profile
rhkr9080
공부방
이전 포스트

[코드트리] 싸움땅

다음 포스트

[코드트리] 산타의 선물공장 2

0개의 댓글