[BOJ] 20058번 마법사 상어와 파이어스톰(C++)

풀이 소요시간 : 60분 초과(실패)

풀긴 풀었는데 시간이 꽤 소요됬다. 탐색 이 필요하긴 한데 굉장히 기본적인 수준이 요구될 뿐이고, 구현 시간의 90% 을 차지하는, 이 문제 난이도가 골드 3이 되게하는 골칫거리는 좌표 변환이였다. 이런 문제는 풀고 암기수준으로 풀이를 기억해야한다. 내가 전에 배열을 회전시키는 문제를 한번이라도 풀어봤더라면 이 문제 푸는데 30분도 안걸렸을 것이다.

이건 반.드.시 외우고 넘어가야한다.

N * N 배열을 시계방향으로 90도 회전시키는 방법!!

필요한 정보 : 배열의 가장 왼쪽 위 좌표 x, y
배열 한 변의 길이 : Size

void Rotation(int x, int y, int Size) {

	for (int i = 0; i < Size; i++)
	{
		for (int j = 0; j < Size; j++)
		{
			int nx = x + j;
			int ny = y + Size - (i + 1);
			Vector.push_back({ nx, ny, Map[x + i][y + j] });
		}
	}

	for (auto E : Vector)
	{
		Map[E.x][E.y] = E.m;
	}

	Vector.clear();
}

가장 왼쪽 위의 좌표 x, y 를 기준으로
해당 Rotation 함수를 구현할 수 있었다.

전체 코드

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

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int N;
int Map[200][200];
int Visit[200][200];
vector<int> Query;

int Sum;
int Max;
int Area = 0; //얼음 덩어리 세기 용도

struct Position {
	int x;
	int y;
	int m;
};
vector<Position> Vector;
vector<pair<int, int>> Melt_Position;

void Input() {
	int Exp, Q;
	cin >> Exp >> Q;
	N = pow(2, Exp);
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> Map[i][j];
		}
	}
	for (int i = 1; i <= Q; i++)
	{
		int E;
		cin >> E;
		Query.push_back(E);
	}
}

void Melt_State(int x, int y) {
	int Cnt = 0;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 1 || ny < 1 || nx > N || ny > N) continue;

		if (Map[nx][ny] > 0) Cnt++;
	}
	if (Cnt < 3 && Map[x][y] > 0)
	{
		Melt_Position.push_back({ x, y });
	}
}

void Rotation(int x, int y, int Size) {

	for (int i = 0; i < Size; i++)
	{
		for (int j = 0; j < Size; j++)
		{
			int nx = x + j;
			int ny = y + Size - (i + 1);
			Vector.push_back({ nx, ny, Map[x + i][y + j] });
		}
	}

	for (auto E : Vector)
	{
		Map[E.x][E.y] = E.m;
	}

	Vector.clear();
}


void Dfs(int x, int y) {
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 1 || ny < 1 || nx > N || ny > N) continue;
		if (Visit[nx][ny] == 1) continue;
		if (Map[nx][ny] < 1) continue;

		Visit[nx][ny] = 1;
		Area++;
		Dfs(nx, ny);
	}
}


int main()
{
	Input();
	for (int Exp : Query)
	{
		int Size = pow(2, Exp);
		//맨 위의 좌표
		for (int i = 1; i <= N; i += Size)
		{
			//맨 왼쪽의 좌표
			for (int j = 1; j <= N; j += Size)
			{
				Rotation(i, j, Size);
			}
		}

		//Melt_Position 에 좌표 삽입
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				Melt_State(i, j);
			}
		}

		//Melt_Position 좌표 얼음 녹이기
		for (auto E : Melt_Position)
		{
			int px = E.first;
			int py = E.second;
			Map[px][py]--;
		}

		Melt_Position.clear();
		//초기화


	}


	//남아있는 얼음의 총 합
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			Sum += Map[i][j];
		}
	}


	//가장 큰 얼음덩어리 넓이 구하기
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (Visit[i][j] == 1) continue;
			if (Map[i][j] < 1) continue;
			
			//영역 체크, 넓이 + 1
			Visit[i][j] = 1;
			Area++;

			//탐색 후 최댓값 갱신
			Dfs(i, j);
			Max = max(Max, Area);

			//초기화
			Area = 0;
		}
	}

	cout << Sum << '\n';
	cout << Max << '\n';

}