본문 바로가기
알고리즘/[ADV] 삼성 SW 역량 테스트 A형

BOJ 23290 : 마법사 상어와 복제 (삼성 SW TEST A형)

by 피로물든딸기 2021. 11. 6.
반응형

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

https://www.acmicpc.net/problem/23290

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

 

먼저, 문제 아래에 설명된 상어의 이동 방법에 대해 구현해보자.

상어의 이동 방법은 상하좌우 = 1, 2, 3, 4 중 3개를 선택하는 중복 조합이다

따라서 43 = 64가지 방법을 미리 구현해둔다.

N과 M (4) - 중복 조합 코드에서 outputList를 고치면 된다.

상하좌우에 대한 경우의 수는 moveList에 저장해둔다.

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

MOVE moveList[70];
int mcnt;

int list[10];

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);
	}
}

 

moveList에는 (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 1), ... , (4, 4, 3), (4, 4, 4)가 담겨있다.

mcnt = 64가 된다.

상어의 좌표를 저장할 구조체와 상어의 현재 위치를 저장할 SHARK_MAP을 선언한다.

물고기의 수가 굉장히 많지만, 물고기의 좌표 (r, c)와 direction 1 ~ 8 로 구분가능하기 때문에

fish[7][7][10] 배열에서 같은 좌표와 같은 방향의 물고기를 한꺼번에 이동하거나 제거하여 연산을 줄인다.

int BOUND[7][7];
int SMELL[7][7];

int M, S;

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

SHARK shark;
int SHARK_MAP[7][7];

int fish[7][7][10];

 

input은 아래와 같이 구현하면 된다.

BOUND 배열은 4 x 4 좌표를 벗어나지 않는지 쉽게 체크하기 위해 만든 배열이다.

그리고 상어의 위치를 SHARK_MAP에 표시한다.

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

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

		scanf("%d %d %d", &fx, &fy, &d);

		fish[fx][fy][d]++;
	}

	scanf("%d %d", &shark.r, &shark.c);
	SHARK_MAP[shark.r][shark.c] = 1;

	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;
}

8 방향과 4 방향 좌표를 아래와 같이 정의한다.

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

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

 

그리고 배열을 통째로 copy하기 위한 함수를 만들어둔다.

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];
}

 

main은 아래와 같다.

input을 받고, 중복 조합으로 상어의 움직이는 경우의 수를 저장한다.

 

1. 물고기를 미리 복제한다.

2. 물고기를 이동한다.

3. 상어를 64번 움직여서 가장 물고기를 많이 잡는 경우를 찾는다. 

 → 같은 물고기를 잡는 경우 사전 순이라는 조건이 있지만, 중복 조합이 이미 사전 순을 반영하고 있다.

 

4. 물고기 냄새를 감소시킨다.

5. 복제 마법 완료.

int main(void)
{
	input();

	DFS(0);

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

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

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

		int step, maxFish;
		step = maxFish = -1;

		for (int i = 0; i < 64; i++)
		{
			int numOfFish = getFish(i);

			if (numOfFish > maxFish)
			{
				maxFish = numOfFish;
				step = i;
			}
		}

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

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

		// 5. 복제 마법 완료
		for (int r = 1; r <= 4; r++)
			for (int c = 1; c <= 4; c++)
				for (int d = 1; d <= 8; d++)
					fish[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 += fish[r][c][d];

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

	return 0;
}

2. 물고기 이동

 

물고기의 이동은 아래와 같이 구현한다.

물고기가 동시에 움직이기 때문에 임시 배열이 필요하다.

 

또한 dr8, dc8은 시계 방향으로 정의하였으나, 물고기가 움직이지 않는 경우는 반시계 방향으로 돌아야한다.

따라서 m = 0 ~ -8로 감소하면서 움직일 수 있는지 check 한다.

SHARK_MAP과 SMELL, BOUND 배열로 물고기의 이동 여부를 쉽게 판단할 수 있다.

이때, m = -8이 되면 모든 방향에 대해 움직임이 불가능하다는 뜻이 되므로,

tmp 배열 좌표에 그대로 물고기를 누적한다.

 

dr8, dc8 배열을 1부터 방향을 정의하였으므로, 반시계 방향 회전시에는 - 1을 빼고 나중에 + 1을 더하였다.

void moveFish()
{
	int tempFish[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++)
				tempFish[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 (fish[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 (SHARK_MAP[nr][nc] || SMELL[nr][nc] || BOUND[nr][nc]) continue;
					else // 이동 가능
					{
						tempFish[nr][nc][(d - 1 + m + 8) % 8 + 1] += fish[r][c][d];
						break;
					}
				}

				if (m == -8) tempFish[r][c][d] += fish[r][c][d];
			}
		}
	}

	copy(fish, tempFish);
}

상어가 물고기를 잡는 64가지 경우의 수

 

moveList 0 ~ 63에 상어의 이동이 저장되어 있다.

따라서 step = 0 ~ 63에 대해 물고기를 얼마나 잡아먹는지 check한다.

int getFish(int step)
{
	SHARK tempShark = shark;
	int tempFish[7][7][10] = { 0 };
	int count;

	copy(tempFish, fish);

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

		nr = tempShark.r + dr4[moveList[step].move[i]];
		nc = tempShark.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 += tempFish[nr][nc][d];
			tempFish[nr][nc][d] = 0;
		}

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

	return count;
}

 

64가지 경우에 대해 getFish로 가장 많이 물고기를 제거하는 경우의 step을 저장하고,

그 step에 대해 moveShark를 실행한다.

int step, maxFish;
step = maxFish = -1;

for (int i = 0; i < 64; i++)
{
	int numOfFish = getFish(i);

	if (numOfFish > maxFish)
	{
		maxFish = numOfFish;
		step = i;
	}
}

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

 

물고기의 이동 여부에 상어의 위치가 포함되어 있다.

따라서 현재 상어의 위치는 0으로 바꿔주고, 최종 위치에 다시 1로 변경한다.

상어가 이동하면서 8 방향에 대한 fish 좌표를 모두 0으로 만들어주고(물고기 제거),

냄새를 SMELL에 남긴다.

SMELL은 2턴 동안 유지되기 때문에 3으로 표시해야 한다.

moveShark 이후에 SMELL 배열을 바로 감소시키기 때문이다.

void moveShark(int step)
{
	SHARK_MAP[shark.r][shark.c] = 0;

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

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

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

			fish[nr][nc][d] = 0;
			SMELL[nr][nc] = 3;
		}

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

	SHARK_MAP[shark.r][shark.c] = 1;
}

 

상어가 이동한 후, 아래의 코드를 실행하면 복제 마법이 완료된다.

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

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

 

마지막 남은 fish를 모두 더해주면 답이 된다.

최종 코드는 아래와 같다.

#include <stdio.h>

int BOUND[7][7];
int SMELL[7][7];

int M, S;

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

SHARK shark;
int SHARK_MAP[7][7];

int fish[7][7][10];

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

MOVE moveList[70];
int mcnt;

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

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

		scanf("%d %d %d", &fx, &fy, &d);

		fish[fx][fy][d]++;
	}

	scanf("%d %d", &shark.r, &shark.c);
	SHARK_MAP[shark.r][shark.c] = 1;

	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;
}

int list[10];

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);
	}
}

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

/* 0, 상 : 1, 좌 : 2, 하 : 3, 우 : 4 */
int dr4[] = { 0, -1, 0, 1, 0 };
int dc4[] = { 0, 0, -1, 0, 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 outputSmell()
{
	printf("smell\n");
	for (int r = 1; r <= 4; r++)
	{
		for (int c = 1; c <= 4; c++)
			printf("%d ", SMELL[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void moveFish()
{
	int tempFish[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++)
				tempFish[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 (fish[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 (SHARK_MAP[nr][nc] || SMELL[nr][nc] || BOUND[nr][nc]) continue;
					else // 이동 가능
					{
						tempFish[nr][nc][(d - 1 + m + 8) % 8 + 1] += fish[r][c][d];
						break;
					}
				}

				if (m == -8) tempFish[r][c][d] += fish[r][c][d];
			}
		}
	}

	copy(fish, tempFish);
}

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 ", fish[r][c][d]);
			putchar('\n');
		}
		putchar('\n');
	}

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

int getFish(int step)
{
	SHARK tempShark = shark;
	int tempFish[7][7][10] = { 0 };
	int count;

	copy(tempFish, fish);

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

		nr = tempShark.r + dr4[moveList[step].move[i]];
		nc = tempShark.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 += tempFish[nr][nc][d];
			tempFish[nr][nc][d] = 0;
		}

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

	return count;
}

void moveShark(int step)
{
	SHARK_MAP[shark.r][shark.c] = 0;

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

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

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

			fish[nr][nc][d] = 0;
			SMELL[nr][nc] = 3;
		}

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

	SHARK_MAP[shark.r][shark.c] = 1;
}

int main(void)
{
	input();

	DFS(0);

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

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

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

		int step, maxFish;
		step = maxFish = -1;

		for (int i = 0; i < 64; i++)
		{
			int numOfFish = getFish(i);

			if (numOfFish > maxFish)
			{
				maxFish = numOfFish;
				step = i;
			}
		}

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

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

		// 5. 복제 마법 완료
		for (int r = 1; r <= 4; r++)
			for (int c = 1; c <= 4; c++)
				for (int d = 1; d <= 8; d++)
					fish[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 += fish[r][c][d];

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

	return 0;
}

실제 A형에서는 각 배열을 잘 초기화하자.

반응형

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

[코드트리] 바이러스 검사 (삼성 SW 역량테스트 2015 하반기 1번 문제)  (1) 2024.06.03
BOJ 23291 : 어항 정리 (삼성 SW TEST A형)  (2) 2021.11.06
BOJ 23289 : 온풍기 안녕! (삼성 SW TEST A형)  (0) 2021.11.06
BOJ 23288 : 주사위 굴리기 2 (삼성 SW TEST A형)  (0) 2021.10.25
BOJ 21611 : 마법사 상어와 블리자드 (삼성 SW TEST A형)  (0) 2021.05.01

관련글

댓글

티스토리툴바