[BOJ]백준 20058번: 마법사 상어와 파이어스톰(C++)/Simulation

https://www.acmicpc.net/problem/20058

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

회전할 부분 배열을 탐색하는 방법을 나눠서 2가지 버전으로 풀었다

왼: L = 1 / 오: L = 2

한 가지 헤맸던 부분은

사방의 얼음 유무를 보고 얼음의 양을 감소시키는 로직에서 탐색 도중에 감소시키는 것이 아닌 탐색이 완료된 뒤 감소시켰어야 했는데

그 부분을 혼동하다 보니 정확한 값을 찾는 데 헤맸다 ㅠ

#include <cstdio>
#include <algorithm>
#define pow2(x) (1<<(x))
using namespace std;

int n, q, s;
int a[129][129], dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
bool visit[129][129];

bool safe(int x, int y) { return x >= 0 && x < n&& y >= 0 && y < n; }

void melting() {
	bool check[129][129] = { false };
	for(int i=0;i<n;i++)
		for (int j = 0; j < n; j++) {
			if (!a[i][j])continue;
			int cnt = 0;
			for (int k = 0; k < 4; k++) {
				int nx = j + dx[k], ny = i + dy[k];
				if (safe(nx, ny)&&a[ny][nx]>0)cnt++;
			}
			if (cnt < 3)check[i][j]=true;
		}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (check[i][j])a[i][j]--;
}

void rotate(int r, int c, int l) {
	int temp[129][129];
	for (int i = 0; i < l; i++)
		for (int j = 0; j < l; j++) {
			temp[i][j] = a[r + l - 1 - j][c + i];
		}

	for (int i = 0; i < l; i++)
		for (int j = 0; j < l; j++) {
			a[r + i][c + j] = temp[i][j];
		}
}

void divide(int r, int c, int l) {
	if (l == pow2(s)) {
		rotate(r, c, l);
		return;
	}
	divide(r, c, l >> 1);
	divide(r + (l >> 1), c, l >> 1);
	divide(r, c + (l >> 1), l >> 1);
	divide(r + (l >> 1), c + (l >> 1), l >> 1);
}

int dfs(int x, int y) {
	if (visit[y][x])return 0;
	visit[y][x] = true;

	int cnt = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (!safe(nx,ny)|| visit[ny][nx] || a[ny][nx] == 0)continue;
		cnt += dfs(nx, ny);
	}
	return cnt;
}

int main() {
	scanf("%d%d", &n, &q);
	n = pow2(n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)scanf("%d", &a[i][j]);
	while (q--) {
		scanf("%d", &s);
		divide(0, 0, n);
		melting();
	}
	int sum = 0,m=0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			sum += a[i][j];
			if (a[i][j]&&!visit[i][j]) {
				int cnt = dfs(j, i);
				m = max(cnt, m);
			}
		}
	printf("%d\n%d", sum, m);
	return 0;
}

 

#include <cstdio>
#include <vector>
#include <algorithm>
#define pii pair<int,int>
#define pow2(x) (1<<(x))
using namespace std;

int n, q, s, len;
int a[129][129], dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
int temp[129][129];
bool visit[129][129];

bool safe(int x, int y) { return x >= 0 && x < len && y >= 0 && y < len; }

void melting() {
	vector<pii> v;
	for (int i = 0; i < len; i++)
		for (int j = 0; j < len; j++) {
			if (!a[i][j])continue;
			int cnt = 0;
			for (int k = 0; k < 4; k++) {
				int nx = j + dx[k], ny = i + dy[k];
				if (safe(nx, ny) && a[ny][nx] > 0)cnt++;
			}
			if (cnt < 3)v.push_back(make_pair(i, j));
		}
	while (!v.empty()) {
		a[v.back().first][v.back().second]--;
		v.pop_back();
	}
}

void divideAndRotate(int s) {
	int l = pow2(s);
	for (int i = 0; i < len; i += l)
		for (int j = 0; j < len; j += l) {
			for (int y = 0; y < l; y++)
				for (int x = 0; x < l; x++) {
					temp[y][x] = a[i + l - 1 - x][j + y];
				}

			for (int y = 0; y < l; y++)
				for (int x = 0; x < l; x++) {
					a[i + y][j + x] = temp[y][x];
				}
		}
}

int dfs(int x, int y) {
	if (visit[y][x])return 0;
	visit[y][x] = true;

	int cnt = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (!safe(nx, ny) || visit[ny][nx] || a[ny][nx] == 0)continue;
		cnt += dfs(nx, ny);
	}
	return cnt;
}

int main() {
	scanf("%d%d", &n, &q); len = pow2(n);
	for (int i = 0; i < len; i++)
		for (int j = 0; j < len; j++)scanf("%d", &a[i][j]);
	while (q--) {
		scanf("%d", &s);
		divideAndRotate(s);
		melting();
	}
	int sum = 0, m = 0;
	for (int i = 0; i < len; i++)
		for (int j = 0; j < len; j++) {
			sum += a[i][j];
			if (a[i][j] && !visit[i][j]) {
				int cnt = dfs(j, i);
				m = max(cnt, m);
			}
		}
	printf("%d\n%d", sum, m);
	return 0;
}