백준 20058 - 마법사 상어와 파이어스톰 (feat. 시계방향 회전, 재귀호출)

문제링크

• 백준 20058

문제설명

• 자세한 설명은 링크를 참고한다.

문제접근

• 핵심은 단계 L 을 입력 받았을 때, 격자를 2^L x 2^L 크기의 부분 격자로 나눈 후 그 부분 격자를 시계방향으로 90도 회전하는 작업이다.
• 회전작업을 재귀적으로 구현했다. 이때, L=0 이 입력되는 경우 1x1 크기의 부분 격자가 되기 때문에 회전 작업이 필요하지 않다는 점에 유의해야 한다.
• 회전작업이 끝나면 인접한 칸을 방문해서 주변 얼음의 개수를 센다. 개수가 3개보다 작은 경우 얼음의 양이 1 감소한다.
  • 줄어든 얼음의 양이 다음 얼음의 인접한 칸을 탐색할 때 영향을 주면 안된다.
• Q번의 파이어스톰이 끝나면 BFS 로 덩어리를 탐색하며 가장 큰 덩어리의 개수를 구한다.
  • 이전에 방문하지 않은 좌표를 선택하여 BFS 를 진행한다. (새로운 덩어리)

구현

#include <iostream>
#include <vector>
#include <cmath>
#include <memory.h>
#include <queue>

#define MAX_N 64
using namespace std;

int board[MAX_N][MAX_N];
int nboard[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
int n;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void RotateSubBoard(int sx, int sy, int len)
{
	if (len < 2)
	{
		return;
	}

	for (int dx = 0; dx < len; dx++)
	{
		nboard[sx + dx][sy + len - 1] = board[sx][sy + dx]; // 윗줄
		nboard[sx + dx][sy] = board[sx + len - 1][sy + dx]; // 아랫줄
		nboard[sx + len - 1][sy + dx] = board[sx + len - 1 - dx][sy + len - 1]; // 오른쪽줄
		nboard[sx][sy + dx] = board[sx + len - 1 - dx][sy]; // 왼쪽줄
	}
	RotateSubBoard(sx + 1, sy + 1, len - 2);
}

int MeltIce()
{
	int ret = 0;
	memcpy(nboard, board, sizeof(board));
	for (int r = 0; r < n; r++)
	{
		for (int c = 0; c < n; c++)
		{
			if (board[r][c] == 0) continue;
			int count = 0;
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = r + dx[dir];
				int ny = c + dy[dir];
				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (board[nx][ny] > 0) count++;
			}
			if (count < 3)
			{
				nboard[r][c] -= 1;
			}
			ret += nboard[r][c];
		}
	}
	memcpy(board, nboard, sizeof(nboard));
	return ret;
}

int bfs(int sx, int sy)
{
	queue<pair<int, int>> q;
	q.push(make_pair(sx, sy));
	visited[sx][sy] = true;
	int ret = 1;
	while (!q.empty())
	{
		pair<int, int> cpos = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cpos.first + dx[dir];
			int ny = cpos.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] == 0) continue;
			visited[nx][ny] = true;
			q.push(make_pair(nx, ny));
			ret++;
		}
	}
	return ret;
}

int GetLargestArea()
{
	memset(visited, false, sizeof(visited));
	int ret = 0;
	for (int r = 0; r < n; r++)
	{
		for (int c = 0; c < n; c++)
		{
			if (visited[r][c]) continue;
			if (board[r][c] == 0) continue;
			ret = max(ret, bfs(r, c));
		}
	}
	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int N, Q;
	cin >> N >> Q;
	n = (int)pow(2.f, (float)N);
	for (int r = 0; r < n; r++)
	{
		for (int c = 0; c < n; c++)
		{
			cin >> board[r][c];
		}
	}

	int L;
	int remain = 0;
	for (int i = 0; i < Q; i++)
	{
		cin >> L;
		int subLen = (int)pow(2.f, (float)L);
		memset(nboard, 0, sizeof(nboard));
		for (int r = 0; r < n; r += subLen)
		{
			for (int c = 0; c < n; c += subLen)
			{
				RotateSubBoard(r, c, subLen);
			}
		}
		if(subLen > 1) memcpy(board, nboard, sizeof(board));
		remain = MeltIce();
	}
	int maxNum = GetLargestArea();
	cout << remain << "\n" << maxNum << endl;
}