[코드트리] 미로 타워 디펜스 (삼성 SW 역량테스트 2021 상반기 오후 2번)

 

SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)

 

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/maze-tower-defense

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

 

미로 타워 디펜스 문제 풀이는 BOJ 21611 : 마법사 상어와 블리자드와 비슷하지만,

방향의 정의와 점수 산정 방식이 다르다.

 

이 문제에서 방향은 아래와 같이 정의한다.

/* →, ↓, ←, ↑ */
int drr[] = { 0, 1, 0, -1 };
int dcc[] = { 1, 0, -1, 0 };

 

그리고 플레이어가 몬스터를 제거할 때, 점수를 추가해야 한다.

	for (int k = 1; k <= s; k++)
	{
		int nr, nc, index;

		nr = sr + drr[d] * k;
		nc = sc + dcc[d] * k;

		score[MAP[nr][nc]]++; // 플레이어가 몬스터를 제거한 경우
		MAP[nr][nc] = 0;

		index = snail[nr][nc];
		indexValue[index] = 0;
	}

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (50 + 5)

int T;
int N, M;
int MAP[MAX][MAX];
int snail[MAX][MAX];
int indexArray[MAX * MAX];
int indexValue[MAX * MAX];
int icnt;

int score[4];

/* ←, ↓, →, ↑ for snail */
int dr[] = { 0, 1, 0, -1 };
int dc[] = { -1, 0, 1, 0 };

/* →, ↓, ←, ↑ */
int drr[] = { 0, 1, 0, -1 };
int dcc[] = { 1, 0, -1, 0 };

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

	for (int i = 1; i <= 3; i++) score[i] = 0;

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

	for (int i = 0; i < N * N; i++) indexArray[i] = i;
}

void output(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 makeSnail(int map[MAX][MAX], int arr[])
{
	int sr, sc, dir, index, size;

	dir = index = size = 0;
	sr = sc = N / 2 + 1;

	map[sr][sc] = arr[index++];
	for (int i = 0; i < 2 * N - 1; i++)
	{
		if (i % 2 == 0) size++;

		for (int s = 0; s < size; s++)
		{
			int nr, nc;

			nr = sr + dr[dir];
			nc = sc + dc[dir];

			/* 순서 주의 */
			map[nr][nc] = arr[index];
			indexValue[index++] = MAP[nr][nc];

			sr = nr;
			sc = nc;
		}

		dir++;
		if (dir == 4) dir = 0;
	}
}

void deleteEmpty(int arr[])
{
	int tcnt = icnt;

	icnt = 1;
	for (int i = 1; i < tcnt; i++)
		if (arr[i] != 0) arr[icnt++] = arr[i];

	/* 남은 칸을 0으로 만든다. */
	for (int i = icnt; i < N * N; i++) arr[i] = 0;
}

int explode(int arr[])
{
	int flag, count, start, tcnt;

	flag = 0;
	start = count = 1;

	tcnt = icnt;
	icnt = 1;
	for (int i = 1; i < tcnt; i++)
	{
		if (arr[i] == arr[i + 1]) count++;
		else
		{
			if (count < 4)
				for (int k = start; k < start + count; k++) arr[icnt++] = arr[k];
			else
			{
				flag = 1;
				score[arr[i]] += count;
			}

			count = 1;
			start = i + 1;
		}
	}

	/* 남은 칸을 0으로 만든다. */
	for (int i = icnt; i < N * N; i++) arr[i] = 0;

	return flag;
}

void makeNewMAP(int arr[])
{
	int newArr[MAX * MAX] = { 0 };
	int ncnt, count;

	ncnt = count = 1;
	for (int i = 1; i < icnt; i++)
	{
		if (arr[i] == arr[i + 1]) count++;
		else
		{
			newArr[ncnt++] = count;
			newArr[ncnt++] = arr[i];

			count = 1;
		}

		if (ncnt == N * N) break;
	}

	for (int i = 1; i < ncnt; i++) arr[i] = newArr[i];
	for (int i = ncnt; i < N * N; i++) arr[i] = 0;

	makeSnail(MAP, arr);
}

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

		makeSnail(snail, indexArray);

		/* simulation */
		for (int i = 0; i < M; i++)
		{
			int d, s, sr, sc;

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

			sr = sc = N / 2 + 1;

			/* 배열 지우기 */
			for (int k = 1; k <= s; k++)
			{
				int nr, nc, index;

				nr = sr + drr[d] * k;
				nc = sc + dcc[d] * k;

				score[MAP[nr][nc]]++; // 플레이어가 몬스터를 제거한 경우
				MAP[nr][nc] = 0;

				index = snail[nr][nc];
				indexValue[index] = 0;
			}

			icnt = N * N;

			deleteEmpty(indexValue);

			while (1)
			{
				int ret = explode(indexValue);

				if (ret == 0) break;

				deleteEmpty(indexValue);
			}

			makeNewMAP(indexValue);
		}

		printf("%d\n", 1 * score[1] + 2 * score[2] + 3 * score[3]);
	}

	return 0;
}