[코드트리] 나무 타이쿤 (삼성 SW 역량테스트 2021 상반기 오후 1번)

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/tree-tycoon

이후 설명 및 입/출력은 링크 참고

 

나무 타이쿤 문제 풀이는 BOJ 21610 : 마법사 상어와 비바라기와 비슷하지만, 정의된 방향이 다르다.

/* 0, →, ↗, ↑, ↖, ←, ↙, ↓, ↘ */
int dr[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int dc[] = { 0, 1, 1, 0, -1, -1, -1, 0, 1 };

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (50 + 5)

int T;
int N, M;
int MAP[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}RC;

RC nutrients[MAX * MAX] = { 0 };
int ncnt;

/* 0, →, ↗, ↑, ↖, ←, ↙, ↓, ↘ */
int dr[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int dc[] = { 0, 1, 1, 0, -1, -1, -1, 0, 1 };

/* ↖, ↗, ↘, ↙ */
int drr[] = { -1, -1, 1, 1 };
int dcc[] = { -1, 1, 1, -1 };

void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);

	nutrients[0].r = N; nutrients[0].c = 1;
	nutrients[1].r = N; nutrients[1].c = 2;
	nutrients[2].r = N - 1; nutrients[2].c = 1;
	nutrients[3].r = N - 1; nutrients[3].c = 2;

	ncnt = 4;
}

void output()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void moveNutrients(int dir, int size)
{
	for (int i = 0; i < ncnt; i++)
	{
		for (int s = 0; s < size; s++)
		{
			int nr, nc;

			nr = nutrients[i].r + dr[dir];
			nc = nutrients[i].c + dc[dir];

			if (nr == N + 1) nr = 1;
			if (nr == 0) nr = N;
			if (nc == N + 1) nc = 1;
			if (nc == 0) nc = N;

			nutrients[i].r = nr;
			nutrients[i].c = nc;
		}
	}
}

void addEnergy()
{
	for (int i = 0; i < ncnt; i++)
		MAP[nutrients[i].r][nutrients[i].c]++;
}

void copyEnergy()
{
	for (int i = 0; i < ncnt; i++)
	{
		int countNutrients = 0;
		for (int dir = 0; dir < 4; dir++)
		{
			int nr, nc;

			nr = nutrients[i].r + drr[dir];
			nc = nutrients[i].c + dcc[dir];

			countNutrients += !!MAP[nr][nc];
		}

		MAP[nutrients[i].r][nutrients[i].c] += countNutrients;
	}
}

int checkCloud(int r, int c)
{
	for (int i = 0; i < ncnt; i++)
		if (nutrients[i].r == r && nutrients[i].c == c) return 1;

	return 0;
}

void makeCloud()
{
	RC newCloud[MAX * MAX] = { 0 };
	int ncnt = 0;

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] < 2) continue;

			/* 현재 구름인지 확인 */
			if (checkCloud(r, c)) continue;

			MAP[r][c] -= 2;

			newCloud[ncnt].r = r;
			newCloud[ncnt++].c = c;
		}
	}

	for (int i = 0; i < ncnt; i++)
		nutrients[i] = newCloud[i];

	ncnt = ncnt;
}

int main()
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		for (int i = 0; i < M; i++)
		{
			int d, s;

			scanf("%d %d", &d, &s);

			moveNutrients(d, s);
			addEnergy();
			copyEnergy();
			makeCloud();
		}

		int sum = 0;
		for (int r = 1; r <= N; r++)
			for (int c = 1; c <= N; c++)
				sum += MAP[r][c];

		printf("%d\n", sum);
	}

	return 0;
}