알고리즘/[ADV] 삼성 SW 역량 테스트 A형

[코드트리] 나무박멸 (삼성 SW 역량테스트 2022 상반기 오후 2번)

피로물든딸기 2024. 6. 23. 18:53
반응형

삼성 A형 전체 링크

 

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

 

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

 

MAP의 정보를 받기 위해 배열을 선언한다.

#define MAX (20 + 5)

#define WALL (-1)

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

 

제초제를 뿌릴 위치와 제초제를 뿌렸을 때 제거될 나무 개수의 정보는 구조체로 관리한다.

typedef struct st
{
	int r;
	int c;
	int count;
}INFO;

 

제초제가 있는 위치는 다른 배열로 관리한다.

int WEEDING[MAX][MAX]; // 제초제

 

대각선 탐색을 위한 dr, dc 배열을 선언한다.

// ↖, ↗, ↘, ↙
int dr[] = {-1, -1, 1, 1};
int dc[] = {-1, 1, 1, -1};

 

input은 다음과 같다.

void input()
{
	scanf("%d %d %d %d", &N, &M, &K, &C);
	
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);
}

시뮬레이션

 

main은 다음과 같이 구성된다.

 

spreadTree : 나무가 성장 + 번식

findMaxDeleteTree : 가장 나무를 많이 제거할 수 있는 위치 찾기

weed : 제초제 뿌리기

sum 변수 : 제거된 나무 누적

 

위를 M번 반복한다.

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();
		
		int sum = 0;
		for (int m = 0; m < M; m++) 
		{
			spreadTree();
			
			INFO target = findMaxDeleteTree();

			weed(target.r, target.c);

			sum += target.count;
		}
			
		printf("%d\n", sum);
	}

	return 0;
}

나무의 성장과 번식

 

나무의 번식을 위해 배열을 만든다. (dr, dc는 대각선 탐색)

상하좌우 탐색은 spreadTree에서만 사용하기 때문에 해당 함수에서만 선언하였다.

	int drr[] = { 0, 1, 0, -1 };
	int dcc[] = { 1, 0, -1, 0 };

 

나무가 없고 벽이 아닌 좌표 (r, c)에 대해, 주변의 나무가 존재하는지 확인하고, MAP[r][c]에 추가한다.

	// 1. 인접한 네 개의 칸 중 나무가 있는 칸의 수만큼 나무가 성장
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 0 || MAP[r][c] == WALL) continue;

			int value = MAP[r][c];
			int count = 0; // 주변 나무의 개수

			for (int i = 0; i < 4; i++)
			{
				int nr, nc;

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

				if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

				if (MAP[nr][nc] > 0) count++;				
			}

			MAP[r][c] += count;
		}
	}

 

나무의 번식은 동시에 이루어진다.

따라서 빈 배열 tmpMAP을 선언하여 번식할 나무를 기록하고, 계산 종료 후, 한 번에 MAP에 저장한다.

이때, 벽이나 빈 공간 뿐만 아니라 제초제가 있는 것도(WEEDIING)도 확인해야 한다.

주변에 번식할 공간이 없는 경우 (count == 0), 나누기를 하지 않도록 continue 처리를 하였다.

	int tmpMAP[MAX][MAX] = { 0 };
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{			
			if (MAP[r][c] == 0 || MAP[r][c] == WALL) continue;

			int value = MAP[r][c];
			int count = 0; // 번식 가능한 칸, 빈 공간의 개수

			for (int i = 0; i < 4; i++)
			{
				int nr, nc;
				
				nr = r + drr[i];
				nc = c + dcc[i];

				if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
				if (MAP[nr][nc] == WALL) continue;

				if (MAP[nr][nc] == 0 && WEEDING[nr][nc] == 0) count++;
			}

			if (count == 0) continue;
				 
			for (int i = 0; i < 4; i++)
			{
				int nr, nc;

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

				if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
				if (MAP[nr][nc] == WALL) continue;

				if (MAP[nr][nc] == 0 && WEEDING[nr][nc] == 0)
					tmpMAP[nr][nc] += MAP[r][c] / count;				
			}
		}
	}

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

 

spreadTree 전체 코드는 다음과 같다.

void spreadTree()
{
	int drr[] = { 0, 1, 0, -1 };
	int dcc[] = { 1, 0, -1, 0 };

	// 1. 인접한 네 개의 칸 중 나무가 있는 칸의 수만큼 나무가 성장
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 0 || MAP[r][c] == WALL) continue;

			int value = MAP[r][c];
			int count = 0; // 주변 나무의 개수

			for (int i = 0; i < 4; i++)
			{
				int nr, nc;

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

				if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

				if (MAP[nr][nc] > 0) count++;				
			}

			MAP[r][c] += count;
		}
	}
			
	int tmpMAP[MAX][MAX] = { 0 };
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{			
			if (MAP[r][c] == 0 || MAP[r][c] == WALL) continue;

			int value = MAP[r][c];
			int count = 0; // 번식 가능한 칸, 빈 공간의 개수

			for (int i = 0; i < 4; i++)
			{
				int nr, nc;
				
				nr = r + drr[i];
				nc = c + dcc[i];

				if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
				if (MAP[nr][nc] == WALL) continue;

				if (MAP[nr][nc] == 0 && WEEDING[nr][nc] == 0) count++;
			}

			if (count == 0) continue;
				 
			for (int i = 0; i < 4; i++)
			{
				int nr, nc;

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

				if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
				if (MAP[nr][nc] == WALL) continue;

				if (MAP[nr][nc] == 0 && WEEDING[nr][nc] == 0)
					tmpMAP[nr][nc] += MAP[r][c] / count;				
			}
		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			MAP[r][c] += tmpMAP[r][c];
}

가장 나무를 많이 제거할 수 있는 위치 찾기

 

(r, c)에 제초제를 놔뒀을 때 제거되는 나무의 수를 구하는 함수를 만들자.

대각선 방향으로 k칸 만큼 탐색하다가, 빈 공간이거나 벽이 있는 경우는 break로 빠져 나와야 한다.

int getDeleteTreeCount(int r, int c)
{
	int sum = 0;

	if (MAP[r][c] == 0) return 0; // 나무가 없는 경우

	sum += MAP[r][c];
	
	for (int i = 0; i < 4; i++)
	{
		for (int k = 1; k <= K; k++)
		{
			int nr, nc;

			nr = r + dr[i] * k;
			nc = c + dc[i] * k;

			if (nr < 1 || nc < 1 || nr > N || nc > N) break;
			if (MAP[nr][nc] == 0 || MAP[nr][nc] == WALL) break;

			sum += MAP[nr][nc];
		}
	}
	
	return sum;
}

 

그리고 이 함수를 모든 좌표에 대해 실행해 가장 큰 나무를 제공하는 좌표를 기록한다. (나무의 수도 저장)

같은 나무의 수를 제거하는 경우, 행이 작은 순서대로, 행도 같다면 열이 작은 순서대로 계산하였다.

INFO findMaxDeleteTree()
{
	INFO result;
	int maxR, maxC, maxTree;
	
	maxR = maxC = maxTree = -1;

	for (int r = 1; r <= N; r++) // 행이 작은 순서대로
	{
		for (int c = 1; c <= N; c++) // 열이 작은 순서대로
		{
			if (MAP[r][c] == WALL) continue;

			int deleteTreeCount = getDeleteTreeCount(r, c);

			if (maxTree < deleteTreeCount)
			{
				maxR = r;
				maxC = c;
				maxTree = deleteTreeCount;
			}
		}
	}

	result.r = maxR;
	result.c = maxC;
	result.count = maxTree;

	return result;
}

제초제 뿌리기

 

제초제는 C년 동안 유지되므로, 제초제가 있는 경우, 제초제 수명을 감소한다.

그리고 제초제를 뿌릴 위치 (r, c)에 C를 기록하고, MAP[r][c]에서 나무를 제거(= 0)한다.

마찬가지로 대각선 방향으로 탐색해서 제초제를 WEEDING에 표시하고, MAP에서는 나무를 제거한다.

나무가 없는 경우, 제초제를 놔두고 break 해야 함에 주의하자. (문제 조건)

void weed(int r, int c)
{	
	for (int i = 1; i <= N; i++)
		for (int k = 1; k <= N; k++)
			if (WEEDING[i][k] != 0) WEEDING[i][k]--;

	MAP[r][c] = 0;
	WEEDING[r][c] = C;
	for (int i = 0; i < 4; i++)
	{
		for (int k = 1; k <= K; k++)
		{
			int nr, nc;

			nr = r + dr[i] * k;
			nc = c + dc[i] * k;

			if (nr < 1 || nc < 1 || nr > N || nc > N) break;
			if (MAP[nr][nc] == WALL) break;
			if (MAP[nr][nc] == 0)
			{
				WEEDING[nr][nc] = C;
				break;
			}

			MAP[nr][nc] = 0;
			WEEDING[nr][nc] = C;
		}
	}
}

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (20 + 5)

#define WALL (-1)

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

typedef struct st
{
	int r;
	int c;
	int count;
}INFO;

int WEEDING[MAX][MAX]; // 제초제

// ↖, ↗, ↘, ↙
int dr[] = {-1, -1, 1, 1};
int dc[] = {-1, 1, 1, -1};
 
void input()
{
	scanf("%d %d %d %d", &N, &M, &K, &C);
	
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);
}

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

void spreadTree()
{
	int drr[] = { 0, 1, 0, -1 };
	int dcc[] = { 1, 0, -1, 0 };

	// 1. 인접한 네 개의 칸 중 나무가 있는 칸의 수만큼 나무가 성장
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 0 || MAP[r][c] == WALL) continue;

			int value = MAP[r][c];
			int count = 0; // 주변 나무의 개수

			for (int i = 0; i < 4; i++)
			{
				int nr, nc;

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

				if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

				if (MAP[nr][nc] > 0) count++;				
			}

			MAP[r][c] += count;
		}
	}
			
	int tmpMAP[MAX][MAX] = { 0 };
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{			
			if (MAP[r][c] == 0 || MAP[r][c] == WALL) continue;

			int value = MAP[r][c];
			int count = 0; // 번식 가능한 칸, 빈 공간의 개수

			for (int i = 0; i < 4; i++)
			{
				int nr, nc;
				
				nr = r + drr[i];
				nc = c + dcc[i];

				if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
				if (MAP[nr][nc] == WALL) continue;

				if (MAP[nr][nc] == 0 && WEEDING[nr][nc] == 0) count++;
			}

			if (count == 0) continue;
				 
			for (int i = 0; i < 4; i++)
			{
				int nr, nc;

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

				if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
				if (MAP[nr][nc] == WALL) continue;

				if (MAP[nr][nc] == 0 && WEEDING[nr][nc] == 0)
					tmpMAP[nr][nc] += MAP[r][c] / count;				
			}
		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			MAP[r][c] += tmpMAP[r][c];
}

// (r, c)에 제초제를 놔둔 경우 삭제되는 나무의 수
int getDeleteTreeCount(int r, int c)
{
	int sum = 0;

	if (MAP[r][c] == 0) return 0; // 나무가 없는 경우

	sum += MAP[r][c];
	
	for (int i = 0; i < 4; i++)
	{
		for (int k = 1; k <= K; k++)
		{
			int nr, nc;

			nr = r + dr[i] * k;
			nc = c + dc[i] * k;

			if (nr < 1 || nc < 1 || nr > N || nc > N) break;
			if (MAP[nr][nc] == 0 || MAP[nr][nc] == WALL) break;

			sum += MAP[nr][nc];
		}
	}
	
	return sum;
}

INFO findMaxDeleteTree()
{
	INFO result;
	int maxR, maxC, maxTree;
	
	maxR = maxC = maxTree = -1;

	for (int r = 1; r <= N; r++) // 행이 작은 순서대로
	{
		for (int c = 1; c <= N; c++) // 열이 작은 순서대로
		{
			if (MAP[r][c] == WALL) continue;

			int deleteTreeCount = getDeleteTreeCount(r, c);

			if (maxTree < deleteTreeCount)
			{
				maxR = r;
				maxC = c;
				maxTree = deleteTreeCount;
			}
		}
	}

	result.r = maxR;
	result.c = maxC;
	result.count = maxTree;

	return result;
}

void weed(int r, int c)
{	
	for (int i = 1; i <= N; i++)
		for (int k = 1; k <= N; k++)
			if (WEEDING[i][k] != 0) WEEDING[i][k]--;

	MAP[r][c] = 0;
	WEEDING[r][c] = C;
	for (int i = 0; i < 4; i++)
	{
		for (int k = 1; k <= K; k++)
		{
			int nr, nc;

			nr = r + dr[i] * k;
			nc = c + dc[i] * k;

			if (nr < 1 || nc < 1 || nr > N || nc > N) break;
			if (MAP[nr][nc] == WALL) break;
			if (MAP[nr][nc] == 0)
			{
				WEEDING[nr][nc] = C;
				break;
			}

			MAP[nr][nc] = 0;
			WEEDING[nr][nc] = C;
		}
	}
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();
		
		int sum = 0;
		for (int m = 0; m < M; m++) 
		{
			spreadTree();
			
			INFO target = findMaxDeleteTree();

			weed(target.r, target.c);

			sum += target.count;
		}
			
		printf("%d\n", sum);
	}

	return 0;
}
반응형