백준 - 마법사 상어와 파이어스톰 (20058)

1. 문제 링크

문제 링크

2. 풀이

BFS와 단순 구현력으로 승부보는 문제입니다.

1. 배열을 회전하기
2. 얼음 녹이기

를 Q번 반복하고
남은 얼음의 합과 제일 큰 덩어리를 출력하면 됩니다.

배열 회전 코드

void rotateRecursive(int n, int y, int x) {
	if (n == L) {
		int size = pow(2, n);

		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++)
				tmp[i][j] = board[i + y][j + x];

		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++)
				board[i + y][j + x] = tmp[size - j - 1][i];

		return;
	}

	int size = pow(2, n - 1);

	rotateRecursive(n - 1, y, x);
	rotateRecursive(n - 1, y, x + size);
	rotateRecursive(n - 1, y + size, x);
	rotateRecursive(n - 1, y + size, x + size);
}

저는 재귀로 구현했습니다.
반복문으로 구현해도 되지만
재귀적으로 생각하니까 더 깔끔하고 구현하기 더 편했습니다.
재귀적으로 1 ~ 4 사분면으로 계속 나누면서 회전하는 식으로 구현했습니다.

얼음 녹이기

for (int i = 0; i < boardSize; i++) {
	for (int j = 0; j < boardSize; j++) {
		if (board[i][j] == 0) continue;

		int count = 0;

		for (int dir = 0; dir < 4; dir++) {
			int y = i + my[dir];
			int x = j + mx[dir];

			if ((isOut(y, x) || board[y][x] == 0) && ++count >= 2) {
				q.push({ i, j });
				break;
			}
		}
	}
}

while (!q.empty()) {
	int y = q.front().first;
	int x = q.front().second;

	q.pop();
	board[y][x]--;
}

얼음을 차례대로 순회하면서 얼음이 없는 면이 두 곳 이상이면 큐에 좌표를 다 담아두고
순회를 마치면 큐에서 하나씩 빼와서 얼음을 녹여줍니다.

int sum = 0, lump = 0;

for (int i = 0; i < boardSize; i++) {
	for (int j = 0; j < boardSize; j++) {
		if (board[i][j] == 0) continue;

		int count = 1;

		q.push({ i, j });
		sum += board[i][j];
		board[i][j] = 0;

		while (!q.empty()) {
			int y = q.front().first;
			int x = q.front().second;

			q.pop();

			for (int dir = 0; dir < 4; dir++) {
				int ny = y + my[dir];
				int nx = x + mx[dir];

				if (isOut(ny, nx) || board[ny][nx] == 0) continue;

				q.push({ ny, nx });
				sum += board[ny][nx];
				board[ny][nx] = 0;
				count++;
			}
		}

		lump = max(lump, count);
	}
}

제일 큰 덩어리를 구하는 방법은 BFS를 이용했습니다.

3. 전체 코드

#define MAX 64
#include <bits/stdc++.h>

using namespace std;

int N, Q, L, boardSize;
int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
int board[MAX][MAX], tmp[MAX][MAX];
queue<pair<int, int>> q;

void rotateRecursive(int n, int y, int x) {
	if (n == L) {
		int size = pow(2, n);

		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++)
				tmp[i][j] = board[i + y][j + x];

		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++)
				board[i + y][j + x] = tmp[size - j - 1][i];

		return;
	}

	int size = pow(2, n - 1);

	rotateRecursive(n - 1, y, x);
	rotateRecursive(n - 1, y, x + size);
	rotateRecursive(n - 1, y + size, x);
	rotateRecursive(n - 1, y + size, x + size);
}

bool isOut(int y, int x) {
	return y < 0 || y >= boardSize || x < 0 || x >= boardSize;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> Q;

	boardSize = pow(2, N);

	for (int i = 0; i < boardSize; i++)
		for (int j = 0; j < boardSize; j++)
			cin >> board[i][j];

	while (Q--) {
		cin >> L;

		rotateRecursive(N, 0, 0);

		for (int i = 0; i < boardSize; i++) {
			for (int j = 0; j < boardSize; j++) {
				if (board[i][j] == 0) continue;

				int count = 0;

				for (int dir = 0; dir < 4; dir++) {
					int y = i + my[dir];
					int x = j + mx[dir];

					if ((isOut(y, x) || board[y][x] == 0) && ++count >= 2) {
						q.push({ i, j });
						break;
					}
				}
			}
		}

		while (!q.empty()) {
			int y = q.front().first;
			int x = q.front().second;

			q.pop();
			board[y][x]--;
		}
	}

	int sum = 0, lump = 0;

	for (int i = 0; i < boardSize; i++) {
		for (int j = 0; j < boardSize; j++) {
			if (board[i][j] == 0) continue;

			int count = 1;

			q.push({ i, j });
			sum += board[i][j];
			board[i][j] = 0;

			while (!q.empty()) {
				int y = q.front().first;
				int x = q.front().second;

				q.pop();

				for (int dir = 0; dir < 4; dir++) {
					int ny = y + my[dir];
					int nx = x + mx[dir];

					if (isOut(ny, nx) || board[ny][nx] == 0) continue;

					q.push({ ny, nx });
					sum += board[ny][nx];
					board[ny][nx] = 0;
					count++;
				}
			}

			lump = max(lump, count);
		}
	}

	cout << sum << '\n' << lump;

	return 0;
}