[백준/BOJ] 백준 20058번 : 마법사 상어와 파이어스톰

www.acmicpc.net/problem/20058

20058번: 마법사 상어와 파이어스톰

회전하는 함수와, 얼음 양 줄일 것을 확인해서 줄이는 함수를 만들었고, 덩어리가 차지하는 칸의 개수를 세는 것은 너비 우선 탐색을 통해 구했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>
using namespace std;

int n, q;
int board[65][65];
int temp[65][65];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int n2;
vector<vector<int>> discovered(65, vector<int>(65, 0));

//회전
void Turn(int len)
{
	for (int i = 1; i <= n2; i = i + len)
	{
		for (int j = 1; j <= n2; j = j + len)
		{

			for (int k = i; k < i + len; k++)
			{
				for (int kk = j; kk < j + len; kk++)
				{
					temp[k][kk] = board[i + len - 1 - kk + j][j + (k - i)];
				}
			}

			for (int k = i; k < i + len; k++)
			{
				for (int kk = j; kk < j + len; kk++)
				{
					board[k][kk] = temp[k][kk];
				}
			}

		}
	}
}

//얼음양 줄일거 줄이기
void Down()
{
	vector<pair<int, int>> down_list;

	for (int i = 1; i <= n2; i++)
		for (int j = 1; j <= n2; j++)
		{
			pair<int, int> here = make_pair(i, j);
			int cnt = 0;

			if (board[here.first][here.second] == 0)
				continue;

			//인접한칸 확인
			for (int i = 0; i < 4; i++)
			{
				pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

				if (there.first >= 1 && there.first <= n2 && there.second >= 1 && there.second <= n2 && board[there.first][there.second] != 0)
				{
					cnt++;
				}
			}

			if (cnt < 3)
				down_list.push_back(here);
		}

	for (int i = 0; i < down_list.size(); i++)
		board[down_list[i].first][down_list[i].second]--; //얼음의 양 줄이기

}

//덩어리가 차지하는 칸의 개수를 센다
int Bfs(pair<int, int> start)
{
	int ret = 0;

	queue<pair<int, int>> q;
	q.push(start);

	discovered[start.first][start.second] = 1;

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		ret++;

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

			if (there.first >= 1 && there.first <= n2 && there.second >= 1 && there.second <= n2 && discovered[there.first][there.second] == 0 && board[there.first][there.second] != 0)
			{
				discovered[there.first][there.second] = 1;
				q.push(there);
			}
		}
	}

	return ret;
}

pair<int, int> Solve()
{
	int ret1 = 0;
	int ret2 = 0;

	for (int i = 1; i <= n2; i++)
		for (int j = 1; j <= n2; j++)
		{
			ret1 += board[i][j];

			if (board[i][j] != 0 && discovered[i][j] == 0)
				ret2 = max(ret2, Bfs(make_pair(i, j)));
		}

	return make_pair(ret1, ret2);
}

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

	cin >> n >> q;

	n2 = pow(2, n);

	for (int i = 1; i <= n2; i++)
		for (int j = 1; j <= n2; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}

	for (int i = 0; i < q; i++)
	{
		int l;
		cin >> l;

		Turn(pow(2, l)); //회전
		
		Down(); //얼음양 줄이기
	}

	pair<int, int> result = Solve();

	cout << result.first << "\n";
	cout << result.second << "\n";

}