[코드트리] 회전하는 빙하 (삼성 SW 역량테스트 2020 하반기 오후 2번)

삼성 A형 전체 링크

 

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

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

 

회전하는 빙하 문제 풀이는 BOJ 20058 : 마법사 상어와 파이어스톰과 회전하는 방법이 다르다.

여기서는 격자가 전체 회전하지 않고, 부분 격자가 모양을 유지한 채로 회전한다.

 

따라서 rotate 구현은 아래와 같다. (격자를 나눈 후, 왼쪽 상단 = 1, 오른쪽 상단 = 2, 왼쪽 하단 = 3, 오른쪽 하단 = 4)

void rotate(int map[MAX][MAX], int sr, int sc, int size)
{
	int half = size / 2;

	for (int r = 0; r < size; r++)
		for (int c = 0; c < size; c++)
			tmpMAP[r][c] = map[sr + r][sc + c];

	// 3 -> 1
	for (int r = 0; r < half; r++)
		for (int c = 0; c < half; c++)
			map[sr + r][sc + c] = tmpMAP[r + half][c];

	// 1 -> 2
	for (int r = 0; r < half; r++)
		for (int c = 0; c < half; c++)
			map[sr + r][sc + c + half] = tmpMAP[r][c];

	// 4 -> 3
	for (int r = 0; r < half; r++)
		for (int c = 0; c < half; c++)
			map[sr + r + half][sc + c] = tmpMAP[r + half][c + half];

	// 2 -> 4
	for (int r = 0; r < half; r++)
		for (int c = 0; c < half; c++)
			map[sr + r + half][sc + c + half] = tmpMAP[r][c + half];
}

 

rotate 구현을 편하게 하기 위해 좌표를 0 부터 시작하도록 수정하였다.

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (64 + 5)

int T;
int N, Q, MAP_SIZE;
int MAP[MAX][MAX];

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

QUEUE queue[MAX * MAX];
int wp, rp;

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

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

	MAP_SIZE = 1 << N;

	for (int r = 0; r < MAP_SIZE; r++)
		for (int c = 0; c < MAP_SIZE; c++)
			scanf("%d", &MAP[r][c]);
}

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

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

	int half = size / 2;

	for (int r = 0; r < size; r++)
		for (int c = 0; c < size; c++)
			tmpMAP[r][c] = map[sr + r][sc + c];

	// 3 -> 1
	for (int r = 0; r < half; r++)
		for (int c = 0; c < half; c++)
			map[sr + r][sc + c] = tmpMAP[r + half][c];

	// 1 -> 2
	for (int r = 0; r < half; r++)
		for (int c = 0; c < half; c++)
			map[sr + r][sc + c + half] = tmpMAP[r][c];

	// 4 -> 3
	for (int r = 0; r < half; r++)
		for (int c = 0; c < half; c++)
			map[sr + r + half][sc + c] = tmpMAP[r + half][c + half];

	// 2 -> 4
	for (int r = 0; r < half; r++)
		for (int c = 0; c < half; c++)
			map[sr + r + half][sc + c + half] = tmpMAP[r][c + half];
}

void meltIce()
{
	int ICE[MAX][MAX] = { 0 };

	for (int r = 0; r < MAP_SIZE; r++)
	{
		for (int c = 0; c < MAP_SIZE; c++)
		{			
			if (MAP[r][c] == 0) continue; 

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

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

				if (nr < 0 || nc < 0 || nr >= MAP_SIZE || nc >= MAP_SIZE)
				{
					cnt++;
					continue;
				}

				if(MAP[nr][nc] == 0) cnt++;
			}

			if (cnt >= 2) ICE[r][c] = 1;
		}
	}

	for (int r = 0; r < MAP_SIZE; r++)
		for (int c = 0; c < MAP_SIZE; c++)
			MAP[r][c] -= ICE[r][c];
}

int BFS(int r, int c, int visit[MAX][MAX])
{
	int cnt;

	wp = rp = 0;

	cnt = 1;

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

	visit[r][c] = 1;

	while (wp > rp)
	{
		QUEUE out = queue[rp++];

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

			if (nr < 0 || nc < 0 || nr >= MAP_SIZE || nc >= MAP_SIZE) continue;

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

				visit[nr][nc] = 1;
				cnt++;
			}
		}
	}

	return cnt;
}

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

	int max = 0;

	for (int r = 0; r < MAP_SIZE; r++)
	{
		for (int c = 0; c < MAP_SIZE; c++)
		{
			if (MAP[r][c] == 0 || visit[r][c] == 1) continue;

			int tmp = BFS(r, c, visit);
			if (max < tmp) max = tmp;
		}
	}

	return max;
}

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

		for (int q = 0; q < Q; q++)
		{
			int L;
			scanf("%d", &L);

			int divide = 1 << L;

			for (int r = 0; r < MAP_SIZE; r += divide)
				for (int c = 0; c < MAP_SIZE; c += divide)
					rotate(MAP, r, c, divide);

			meltIce();
		}

		int sum = 0;
		for (int r = 0; r < MAP_SIZE; r++)
			for (int c = 0; c < MAP_SIZE; c++)
				sum += MAP[r][c];

		printf("%d\n%d\n", sum, findBigIce());
	}

	return 0;
}