[코드트리] 고대 문명 유적 탐사 (삼성 SW 역량테스트 2024 상반기 오전 1번)

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

 

삼성 A형 전체 링크

 

참고

- N x N 2차원 배열 뒤집기, 회전하기 (Rotate, Flip 2D Array)

- BOJ 2667 : 단지번호붙이기

 

https://www.codetree.ai/training-field/frequent-problems/problems/ancient-ruin-exploration

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

 

좌표를 관리할 구조체를 선언한다.

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

 

4방향 탐색을 위한 배열을 선언한다.

int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

 

input은 다음과 같다.

주어진 2차원 배열과 유물 조각은 MAP과 PIECE에 저장한다.

#define MAX (10)

int T;
int K, M;

int MAP[MAX][MAX];
int PIECE[300 + 50];
int pcnt;

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

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

	pcnt = 0;
	for (int m = 0; m < M; m++) scanf("%d", &PIECE[m]);
}

 

2차원 배열을 회전하기 위한 함수는 다음과 같다.

문제의 경우 중심에서 회전하지만, 실제 구현은 좌측 상단(= sr, sc)을 보고 90도 회전하였다.

void copyMap(int src[MAX][MAX], int dest[MAX][MAX])
{
	for (int i = 0; i < MAX; i++)
		for (int k = 0; k < MAX; k++)
			src[i][k] = dest[i][k];
}

void rotate(int map[MAX][MAX], int sr, int sc)
{
	int temp[MAX][MAX] = { 0 };

	copyMap(temp, map);

	for (int r = 0; r < 3; r++)
		for (int c = 0; c < 3; c++)
			map[r + sr][c + sc] = temp[3 - 1 - c + sr][r + sc];
}

 

main은 다음과 같다.

시뮬레이션 결과가 0인 경우 종료한다.

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

		for (int k = 0; k < K; k++)
		{
			int result = simulate();

			if (result == 0) break;

			printf("%d ", result);
		}
	}

	return 0;
}

 

시뮬레이션은 다음과 같이 진행된다.

 

1) 회전 각도가 작고, 열이 작고, 행이 작은 순서대로 얼마나 유물이 획득되는지 (getItem) 확인한다.

2) 유물을 새로 들고온다. (setItem)

3) 현 상태에서 유물을 가져온다. (getItem)

ㄴ 가져올 수 있는 유물이 0이 되는 경우 종료한다.

int simulate()
{
	int sum = 0;
	int maxMap[MAX][MAX] = { 0 };
	int maxItemCount = 0;

	// 회전 각도가 작고
	for (int rot = 1; rot <= 3; rot++)
	{
		// 열이 작고
		for (int c = 1; c <= 3; c++)
		{
			// 행이 작은 순
			for (int r = 1; r <= 3; r++)
			{
				int tMap[MAX][MAX] = { 0 };

				copyMap(tMap, MAP);

				for (int rotCnt = 1; rotCnt <= rot; rotCnt++) rotate(tMap, r, c);

				int itemCount = getItem(tMap);

				if (maxItemCount < itemCount)
				{
					maxItemCount = itemCount;
					copyMap(maxMap, tMap);
				}
			}
		}
	}

	if (maxItemCount == 0) return 0;

	sum += maxItemCount;

	while (1)
	{
		setItem(maxMap);

		int itemCount = getItem(maxMap);

		if (itemCount == 0) break;

		sum += itemCount;
	}

	copyMap(MAP, maxMap);

	return sum;
}

---

유물 획득

 

유물 획득은 다음과 같다.

모든 좌표에 대해 BFS로 3개 이상 같은 숫자가 있는지 판단한다.

3개 이상인 경우 다시 BFS로 지운다.

(개수를 세면서 지울 경우, 3개 미만의 유물에 대해 복구를 하기가 힘들기 때문에 함수를 분리하였다.)

int getItem(int map[MAX][MAX])
{
	int visit[MAX][MAX] = { 0 };

	int sum = 0;
	for (int r = 1; r <= 5; r++)
	{
		for (int c = 1; c <= 5; c++)
		{
			if (visit[r][c] != 0) continue;

			int count = bfsCount(map, visit, r, c);

			if (count < 3) continue;

			sum += count;
			bfsDelete(map, r, c);
		}
	}

	return sum;
}

 

단지번호붙이기를 참고해서, 2차원 배열에 연속된 같은 번호를 구하는 함수를 만든다.

int bfsCount(int map[MAX][MAX], int visit[MAX][MAX], int sr, int sc)
{
	RC queue[MAX * MAX] = { 0 };
	int rp, wp, cnt, number;

	rp = wp = 0;

	cnt = 1;

	queue[wp].r = sr;
	queue[wp++].c = sc;

	visit[sr][sc] = 1;

	number = map[sr][sc];

	while (rp < wp)
	{
		RC out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (visit[nr][nc] == 0 && map[nr][nc] == number)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = 1;

				cnt++;
			}
		}
	}

	return cnt;
}

 

위의 bfsCount와 비슷하지만, bfsDelete는 map을 0으로 변경하는 코드가 추가된다.

또한 같은 번호만 지우면 되기 때문에 해당 좌표에서 visit을 새로 선언하여 처리하였다.

void bfsDelete(int map[MAX][MAX], int sr, int sc)
{
	RC queue[MAX * MAX] = { 0 };
	int rp, wp, number;

	int visit[MAX][MAX] = { 0 };

	rp = wp = 0;

	queue[wp].r = sr;
	queue[wp++].c = sc;

	number = map[sr][sc];

	map[sr][sc] = 0;

	while (rp < wp)
	{
		RC out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (visit[nr][nc] == 0 && map[nr][nc] == number)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = 1;

				map[nr][nc] = 0;
			}
		}
	}
}

 

유물을 추가하는 함수는 다음과 같다.

열 번호가 작고 행 번호가 큰 순서대로 PIECE 배열로부터 가져온다.

void setItem(int map[MAX][MAX])
{
	for (int c = 1; c <= 5; c++)
		for (int r = 5; r >= 1; r--)
			if (map[r][c] == 0) map[r][c] = PIECE[pcnt++];
}

---

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (10)

int T;
int K, M;

int MAP[MAX][MAX];
int PIECE[300 + 50];
int pcnt;

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

int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

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

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

	pcnt = 0;
	for (int m = 0; m < M; m++) scanf("%d", &PIECE[m]);
}

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

void copyMap(int src[MAX][MAX], int dest[MAX][MAX])
{
	for (int i = 0; i < MAX; i++)
		for (int k = 0; k < MAX; k++)
			src[i][k] = dest[i][k];
}

void rotate(int map[MAX][MAX], int sr, int sc)
{
	int temp[MAX][MAX] = { 0 };

	copyMap(temp, map);

	for (int r = 0; r < 3; r++)
		for (int c = 0; c < 3; c++)
			map[r + sr][c + sc] = temp[3 - 1 - c + sr][r + sc];
}

// 유물의 개수를 확인
int bfsCount(int map[MAX][MAX], int visit[MAX][MAX], int sr, int sc)
{
	RC queue[MAX * MAX] = { 0 };
	int rp, wp, cnt, number;

	rp = wp = 0;

	cnt = 1;

	queue[wp].r = sr;
	queue[wp++].c = sc;

	visit[sr][sc] = 1;

	number = map[sr][sc];

	while (rp < wp)
	{
		RC out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (visit[nr][nc] == 0 && map[nr][nc] == number)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = 1;

				cnt++;
			}
		}
	}

	return cnt;
}

void bfsDelete(int map[MAX][MAX], int sr, int sc)
{
	RC queue[MAX * MAX] = { 0 };
	int rp, wp, number;

	int visit[MAX][MAX] = { 0 };

	rp = wp = 0;

	queue[wp].r = sr;
	queue[wp++].c = sc;

	number = map[sr][sc];

	map[sr][sc] = 0;

	while (rp < wp)
	{
		RC out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (visit[nr][nc] == 0 && map[nr][nc] == number)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = 1;

				map[nr][nc] = 0;
			}
		}
	}
}

int getItem(int map[MAX][MAX])
{
	int visit[MAX][MAX] = { 0 };

	int sum = 0;
	for (int r = 1; r <= 5; r++)
	{
		for (int c = 1; c <= 5; c++)
		{
			if (visit[r][c] != 0) continue;

			int count = bfsCount(map, visit, r, c);

			if (count < 3) continue;

			sum += count;
			bfsDelete(map, r, c);
		}
	}

	return sum;
}

void setItem(int map[MAX][MAX])
{
	for (int c = 1; c <= 5; c++)
		for (int r = 5; r >= 1; r--)
			if (map[r][c] == 0)	map[r][c] = PIECE[pcnt++];
}

int simulate()
{
	int sum = 0;
	int maxMap[MAX][MAX] = { 0 };
	int maxItemCount = 0;

	// 회전 각도가 작고
	for (int rot = 1; rot <= 3; rot++)
	{
		// 열이 작고
		for (int c = 1; c <= 3; c++)
		{
			// 행이 작은 순
			for (int r = 1; r <= 3; r++)
			{
				int tMap[MAX][MAX] = { 0 };

				copyMap(tMap, MAP);

				for (int rotCnt = 1; rotCnt <= rot; rotCnt++) rotate(tMap, r, c);

				int itemCount = getItem(tMap);

				if (maxItemCount < itemCount)
				{
					maxItemCount = itemCount;
					copyMap(maxMap, tMap);
				}
			}
		}
	}

	if (maxItemCount == 0) return 0;

	sum += maxItemCount;

	while (1)
	{
		setItem(maxMap);

		int itemCount = getItem(maxMap);

		if (itemCount == 0) break;

		sum += itemCount;
	}

	copyMap(MAP, maxMap);

	return sum;
}

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

		for (int k = 0; k < K; k++)
		{
			int result = simulate();

			if (result == 0) break;

			printf("%d ", result);
		}
	}

	return 0;
}