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

sol : 97' 55''

• 수행 시간 : 68ms
• 메모리 : 2064KB

Learnings

• 확실히 쉽게 느껴진다. 회전 구현만 안막혔으면 훨씬 빨리 풀었을듯.
• 상대 좌표에 따른 회전 공식도 너무 어렵게 계산할 필요가 없었다.
• 이전엔 전역에서 직접 좌표를 수학적으로 계산해서 넣었는데, 그냥 각 위치마다 offset을 더해주는 식으로만 해주면 매우 간단했다.
  [이전 ver]
  tempGrid[gj + ai - aj][l - gi + ai + aj - 1] = grid[gi][gj];
  [현재 ver]

	for (int jj = 0; jj < total_len; jj += ds_len) {
		for (int i = 0; i < ds_len; i++) {
			for (int j = 0; j < ds_len; j++) {
				tempGrid[ii + j][jj + ds_len - i - 1] = grid[ii + i][jj + j];
			}
		}
	}
}```

#include <iostream>
#include <queue>
#include <utility>

#define MAX_N 64
#define MAX_Q 1000

using namespace std;

int n, q;
int grid[MAX_N][MAX_N];
int orders[MAX_Q];
int total_len, ds_len;
int tempGrid[MAX_N][MAX_N];
// 상, 하, 좌, 우
int ds[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

bool visited[MAX_N][MAX_N];

void Init() {
	cin >> n >> q;
	total_len = 1 << n;
	for (int i = 0; i < total_len; i++) {
		for (int j = 0; j < total_len; j++) {
			cin >> grid[i][j];
		}
	}

	for (int i = 0; i < q; i++) {
		cin >> orders[i];
	}
}

bool InGrid(int i, int j) {
	return 0 <= i && i < total_len && 0 <= j && j < total_len;
}

void DupGrid(int from[MAX_N][MAX_N], int to[MAX_N][MAX_N]) {
	for (int i = 0; i < total_len; i++) {
		for (int j = 0; j < total_len; j++) {
			to[i][j] = from[i][j];
		}
	}
}

void InitTempGrid() {
	for (int i = 0; i < total_len; i++) {
		for (int j = 0; j < total_len; j++) {
			tempGrid[i][j] = 0;
		}
	}
}

void Rotate(int level) {
	ds_len = 1 << level;

	InitTempGrid();

	for (int ii = 0; ii < total_len; ii += ds_len) {
		for (int jj = 0; jj < total_len; jj += ds_len) {
			for (int i = 0; i < ds_len; i++) {
				for (int j = 0; j < ds_len; j++) {
					tempGrid[ii + j][jj + ds_len - i - 1] = grid[ii + i][jj + j];
				}
			}
		}
	}

	DupGrid(tempGrid, grid);
}

void Melt() {
	DupGrid(grid, tempGrid);

	for (int i = 0; i < total_len; i++) {
		for (int j = 0; j < total_len; j++) {
			int cnt = 0;
			for (int d = 0; d < 4; d++) {
				int ni = i + ds[d][0], nj = j + ds[d][1];

				if (!InGrid(ni, nj)) continue;
				if (grid[ni][nj] > 0) cnt++;
			}

			if (cnt < 3 && grid[i][j] > 0) tempGrid[i][j]--;
		}
	}

	DupGrid(tempGrid, grid);
}

int GetCurArea(int i, int j) {
	queue<pair<int, int>> q;
	visited[i][j] = true;
	int curArea = 1;

	q.push({ i, j });
	while (!q.empty()) {
		int ci = q.front().first, cj = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];

			if (InGrid(ni, nj) && !visited[ni][nj] && grid[ni][nj] > 0) {
				curArea++;
				q.push({ ni, nj });
				visited[ni][nj] = true;
			}
		}
	}

	return curArea;
}

void GetBiggestArea() {
	int maxArea = 0;
	for (int i = 0; i < total_len; i++) {
		for (int j = 0; j < total_len; j++) {
			if (visited[i][j] || grid[i][j] == 0) continue;

			maxArea = max(maxArea, GetCurArea(i, j));
		}
	}
	cout << maxArea << '\n';
}

void GetTotalIce() {
	int total = 0;
	for (int i = 0; i < total_len; i++) {
		for (int j = 0; j < total_len; j++) {
			if (grid[i][j] <= 0) continue;

			total += grid[i][j];
		}
	}
	cout << total << '\n';
}

int main() {
	Init();

	for (int i = 0; i < q; i++) {
		// 1. Rotate
		Rotate(orders[i]);

		// 2. Melt
		Melt();
	}

	GetTotalIce();
	GetBiggestArea();

	return 0;
}