[baekjoon] 20058

마법사 상어와 파이어스톰

문제

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.

파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

입력

첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.

출력

첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.

제한

• 2 ≤ N ≤ 6
• 1 ≤ Q ≤ 1,000
• 0 ≤ A[r][c] ≤ 100
• 0 ≤ Li ≤ N

풀이

주어진 L에 따라 회전시켜야 하는 격자의 크기가 달라진다.

회전시키는 것을 구현하는 게 가장 골치 아팠다.

주어진 L에 맞춰 회전을 마치고 나면 BFS로 가장 넓은 덩어리를 계산했다.

 

테스트 케이스가 계속 맞지 않아서 뭐가 틀렸는지 계속 찾아봤다...

몇 시간 만에 눈치챈 것은 얼음이 동시에 녹아 야하기 때문에 녹을 좌표를 저장했다가 탐색이 끝난 후 감소시켜줘야 한다.

그리고 L = 0 일 때는 격자의 크기가 1 X 1 이므로 회전하지 않은 것과 같다.

 

#include <iostream>
#include <queue>

using namespace std;

int board[64][64];
int n, q, r, lq[1000];

bool isOut(int x, int y) {
	if (x >= r || y >= r || x < 0 || y < 0)return true;
	else return false;
}

int pow2(int i) {
	int num = 1;
	while (i != 0)i--, num *= 2;

	return num;
}

void input() {
	cin >> n >> q;

	r = pow2(n);
	for (int x = 0; x < r; x++) {
		for (int y = 0; y < r; y++)cin >> board[x][y];
	}
	for (int i = 0; i < q; i++)cin >> lq[i];
}

void firestorm(int range) {
	int temp[64][64];


	for (int x = 0, y = 0; x < r;) {
		
		//rotate
		int row = x + range;
		int col = y + range;
		for (int i = 0; i < range; i++) {
			for (int j = 0; j < range; j++) {
				temp[x+j][y+range - i - 1] = board[x + i][y + j];
			}
		}
		y += range;
		if (y == r)x += range, y = 0;

	}

	//copy
	for (int x = 0; x < r; x++) {
		for (int y = 0; y < r; y++) {
			board[x][y] = temp[x][y];
		}
	}
}

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

void melt() {
	queue<pair<int, int>> q;
	for (int x = 0; x < r; x++) {
		for (int y = 0; y < r; y++) {
			int ccnt = 0;
			for (int z = 0; z < 4; z++) {
				int nx = x + dx[z];
				int ny = y + dy[z];
				if (isOut(nx, ny))continue;
				else if (board[nx][ny] > 0)ccnt++;
			}
			if (ccnt < 3 && board[x][y] != 0)q.push({ x,y });
		}
	}
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		board[x][y]--;
	}
}
int sums() {
	int sum = 0;
	for (int x = 0; x < r; x++) {
		for (int y = 0; y < r; y++) {
			sum += board[x][y];
		}
	}
	return sum;
}
bool visit[64][64];

int mass() {
	int result = 0;
	queue<pair<int, int>> q;
	for (int x = 0; x < r; x++) {
		for (int y = 0; y < r; y++) {
			if (board[x][y] == 0) {
				visit[x][y] = true;
				continue;
			}
			if (visit[x][y])continue;
			
			int ccnt = 0;
			q.push({ x,y });
			visit[x][y] = true;
			while (!q.empty()) {
				int cx = q.front().first;
				int cy = q.front().second;
				q.pop();
			
				ccnt++;

				for (int i = 0; i < 4; i++) {
					int nx = cx + dx[i];
					int ny = cy + dy[i];
					if (visit[nx][ny] || isOut(nx, ny))continue;
					visit[nx][ny] = true;
					if (board[nx][ny] > 0) q.push({ nx, ny });
				}
			}
			if (result < ccnt)result = ccnt;
		}
	}
	return result;
}

void solve() {
	int sum = 0, m;
	//round L
	for (int l = 0; l < q; l++) {
		firestorm(pow2(lq[l]));
		melt();
	}
	sum = sums();
	m = mass();


	cout << sum << "\n" << m;
}

int main() {
	input();
	solve();
}