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

[코드트리] 팩맨 (삼성 SW 역량테스트 2021 하반기 오후 1번)

피로물든딸기 2024. 6. 9. 00:57
반응형

삼성 A형 전체 링크

 

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

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

 

팩맨 문제 풀이는 BOJ 23290 : 마법사 상어와 복제와 비슷하지만, 방향의 정의가 다르다.

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

 

주어진 방향이 반시계 방향이라서, 반시계 방향과 관련된 구현도 수정하였다.

	int m;
	for (m = 0; m < 8; m++) // 반시계 방향 회전
	{
		int nr, nc;

		nr = r + dr8[(d - 1 + m + 8) % 8 + 1];
		nc = c + dc8[(d - 1 + m + 8) % 8 + 1];

		// 팩맨이 있거나, 시체, 격자의 범위의 경우는 반시계방향 회전
		if (PACKMAN_MAP[nr][nc] || DEAD[nr][nc] || BOUND[nr][nc]) continue;
		else // 이동 가능
		{
			tempMonster[nr][nc][(d - 1 + m + 8) % 8 + 1] += monster[r][c][d];
			break;
		}
	}

	if (m == 8) tempMonster[r][c][d] += monster[r][c][d];

 

 

전체 코드는 다음과 같다.

#include <stdio.h>

int T;
int M, TURN;

int BOUND[7][7];
int DEAD[7][7];

typedef struct st1
{
	int r;
	int c;
}PACKMAN;

PACKMAN packMan;
int PACKMAN_MAP[7][7];

int monster[7][7][10];

typedef struct st2
{
	int move[3];
}MOVE;

MOVE moveList[70];
int mcnt;

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

/* 0, 상 : 1, 좌 : 2, 하 : 3, 우 : 4 */
int dr4[] = { 0, -1, 0, 1, 0 };
int dc4[] = { 0, 0, -1, 0, 1 };

int list[10];

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

	scanf("%d %d", &packMan.r, &packMan.c);

	for (int i = 0; i < 7; i++)
		for (int k = 0; k < 7; k++)
			PACKMAN_MAP[i][k] = 0;

	for (int i = 0; i < 7; i++)
		for (int k = 0; k < 7; k++)
			for (int d = 0; d < 10; d++)
				monster[i][k][d] = 0;

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

		scanf("%d %d %d", &fr, &fc, &d);

		monster[fr][fc][d]++;
	}

	PACKMAN_MAP[packMan.r][packMan.c] = 1;

	for (int r = 0; r <= 5; r++)
		for (int c = 0; c <= 5; c++)
			DEAD[r][c] = 0;

	for (int r = 0; r <= 5; r++)
		for (int c = 0; c <= 5; c++)
			BOUND[r][c] = 1;

	for (int r = 1; r <= 4; r++)
		for (int c = 1; c <= 4; c++)
			BOUND[r][c] = 0;
}

void outputList()
{
	//for (int i = 0; i < 3; i++) printf("%d ", list[i]);  putchar('\n');

	moveList[mcnt].move[0] = list[0];
	moveList[mcnt].move[1] = list[1];
	moveList[mcnt++].move[2] = list[2];
}

void DFS(int L)
{
	if (L == 3)
	{
		outputList();
		return;
	}

	for (int i = 1; i <= 4; i++)
	{
		list[L] = i;

		DFS(L + 1);
	}
}

void copy(int dest[7][7][10], int src[7][7][10])
{
	for (int r = 1; r <= 4; r++)
		for (int c = 1; c <= 4; c++)
			for (int d = 1; d <= 8; d++)
				dest[r][c][d] = src[r][c][d];
}

void outputDead()
{
	printf("dead\n");
	for (int r = 1; r <= 4; r++)
	{
		for (int c = 1; c <= 4; c++)
			printf("%d ", DEAD[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void moveMonster()
{
	int tempMonster[7][7][10] = { 0 };

	for (int r = 1; r <= 4; r++)
		for (int c = 1; c <= 4; c++)
			for (int d = 1; d <= 8; d++)
				tempMonster[r][c][d] = 0;

	for (int r = 1; r <= 4; r++)
	{
		for (int c = 1; c <= 4; c++)
		{
			for (int d = 1; d <= 8; d++)
			{
				if (monster[r][c][d] == 0) continue;

				int m;
				for (m = 0; m < 8; m++) // 반시계 방향 회전
				{
					int nr, nc;

					nr = r + dr8[(d - 1 + m + 8) % 8 + 1];
					nc = c + dc8[(d - 1 + m + 8) % 8 + 1];

					// 팩맨이 있거나, 시체, 격자의 범위의 경우는 반시계방향 회전
					if (PACKMAN_MAP[nr][nc] || DEAD[nr][nc] || BOUND[nr][nc]) continue;
					else // 이동 가능
					{
						tempMonster[nr][nc][(d - 1 + m + 8) % 8 + 1] += monster[r][c][d];
						break;
					}
				}

				if (m == 8) tempMonster[r][c][d] += monster[r][c][d];
			}
		}
	}

	copy(monster, tempMonster);
}

void output()
{
	for (int d = 1; d <= 8; d++)
	{
		printf("d : %d\n", d);

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

	printf("---------------------------------\n");
}

int getMonster(int step)
{
	PACKMAN tempPackMan = packMan;
	int tempMonster[7][7][10] = { 0 };
	int count;

	copy(tempMonster, monster);

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

		nr = tempPackMan.r + dr4[moveList[step].move[i]];
		nc = tempPackMan.c + dc4[moveList[step].move[i]];

		if (nr < 1 || nc < 1 || nr > 4 || nc > 4) return -1; // 격자가 벗어나는 경우는 종료.

		for (int d = 1; d <= 8; d++)
		{
			count += tempMonster[nr][nc][d];
			tempMonster[nr][nc][d] = 0;
		}

		tempPackMan.r = nr;
		tempPackMan.c = nc;
	}

	return count;
}

void movePackMan(int step)
{
	PACKMAN_MAP[packMan.r][packMan.c] = 0;

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

		nr = packMan.r + dr4[moveList[step].move[i]];
		nc = packMan.c + dc4[moveList[step].move[i]];

		for (int d = 1; d <= 8; d++)
		{
			if (monster[nr][nc][d] == 0) continue;

			monster[nr][nc][d] = 0;
			DEAD[nr][nc] = 3;
		}

		packMan.r = nr;
		packMan.c = nc;
	}

	PACKMAN_MAP[packMan.r][packMan.c] = 1;
}

int main(void)
{
	DFS(0);

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

		for (int i = 0; i < TURN; i++)
		{
			int copyMagic[7][7][10] = { 0 };

			// 1. 복제
			copy(copyMagic, monster);

			// 2. 물고기 이동
			moveMonster();

			int step, maxMonster;
			step = maxMonster = -1;

			for (int i = 0; i < 64; i++)
			{
				int numOfMonster = getMonster(i);

				if (numOfMonster > maxMonster)
				{
					maxMonster = numOfMonster;
					step = i;
				}
			}

			// 3. 상어 이동
			movePackMan(step);

			// 4. 물고기 냄새 1 감소
			for (int r = 1; r <= 4; r++)
				for (int c = 1; c <= 4; c++)
					if (DEAD[r][c]) DEAD[r][c]--;

			// 5. 복제 마법 완료
			for (int r = 1; r <= 4; r++)
				for (int c = 1; c <= 4; c++)
					for (int d = 1; d <= 8; d++)
						monster[r][c][d] += copyMagic[r][c][d];
		}

		int count = 0;
		for (int r = 1; r <= 4; r++)
			for (int c = 1; c <= 4; c++)
				for (int d = 1; d <= 8; d++)
					count += monster[r][c][d];

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

	return 0;
}
반응형