문제
$N\times N$정사각형 격자판이 있다. 각 칸에는 초기 얼음의 양이 주어진다. 이 격자판에서 할 ‘파이어스톰’이라는 연산이 정의되는데, 이 연산을 주어진 입력에 따라 했을 때 마지막에 남아있는 얼음의 양의 합과 가장 큰 연결된 얼음 덩어리 크기를 찾는 문제이다.
파이어스톰 연산은 다음과 같다. 주어진 변수 $L$에 대해서, 전체 격자를 $2^L \times 2^L$크기의 부분격자로 나눈 후 각 부분격자를 시계방향으로 회전 시킨다. 그 다음, 어떤 칸$(r,c)$에 인접(상하좌우)한 칸들 중 얼음이 있는 칸이 2개 이하라면 $(r,c)$의 얼음의 양을 1 줄인다.
접근
문제 설명이 다소 복잡하지만, 결국 핵심은 (1) 부분격자로 어떻게 나누고, 각 부분격자에서 회전은 어떻게 구현해야 하는지 (2) 가장 큰 연결된 얼음 덩어리 크기는 어떻게 구할지 이다.
(1)의 경우 두 개의 for문을 이용하여 먼저 각 부분격자의 가장 위쪽, 왼쪽 모서리의 좌표를 뽑아냈다. 이 점을 $(row, col)$이라 하면, 시계방향 90도 회전은 다음과 같이 구현할 수 있다. 임시배열 temp, 원래 배열board, 현재 부분격자의 크기 len이라 하면,
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
temp[row + j][col + len - 1 - i] = board[row + i][col + j];
}
}
이다. 기준점 $(row,col)$ 기준으로 좌표를 어떻게 표현하는지 그려서 생각해보면 어렵지 않다.
(2)의 경우 간단한 DFS이다. visited배열에 방문 여부를 저장하고, 모든 칸을 이중 for문으로 돌면서 아직 방문하지 않았다면 dfs(row, col)를 호출해주었다. 네 개의 방향을 살펴보아 유효한 좌표면 재귀적으로 호출하도록 구현하였다.
주의할 점
처음에 문제 설명과 테스트 케이스를 읽고 언제 얼음이 줄어드는지 이해가 잘 안되었다. 인접한 칸중 얼음이 있는 칸이 2개 이하면 얼음이 줄어드므로, 최소한 네 귀퉁이에서는 얼음이 줄어드게 된다.
테케중에 덩어리 0인 케이스가 없으므로, 이 경우에도 원하는 대로 출력되는지 유의하자.
Code
링크#include <algorithm>
#include <iostream>
using namespace std;
int N, Q, board_size;
int board[64][64];
int temp[64][64];
bool visited[64][64] = {false};
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int sum = 0;
// rotate and check ice-melting condition.
void firestrom(int len) {
for (int row = 0; row < board_size; row += len) {
for (int col = 0; col < board_size; col += len) {
// rotate for each subgrid, given its top-left point (row,col)
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
temp[row + j][col + len - 1 - i] = board[row + i][col + j];
}
}
}
}
// check for ice-melting condition
for (int i = 0; i < board_size; i++) {
for (int j = 0; j < board_size; j++) {
int ice_count = 0;
for (int d = 0; d < 4; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
if (0 <= ni && ni < board_size && 0 <= nj && nj < board_size && temp[ni][nj] > 0) {
ice_count++;
}
}
if (ice_count >= 3) {
board[i][j] = temp[i][j];
} else {
board[i][j] = max(0, temp[i][j] - 1);
}
}
}
}
// return the number of connected ices adjacent to (row, col)
int dfs(int row, int col) {
int ret = 0;
for (int d = 0; d < 4; d++) {
int nrow = row + dx[d];
int ncol = col + dy[d];
if (0 <= nrow && nrow < board_size && 0 <= ncol && ncol < board_size && !visited[nrow][ncol] && board[nrow][ncol] > 0) {
visited[nrow][ncol] = true;
ret += 1 + dfs(nrow, ncol);
}
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// get input
cin >> N >> Q;
board_size = 1 << N;
for (int i = 0; i < board_size; i++) {
for (int j = 0; j < board_size; j++) {
cin >> board[i][j];
}
}
// do firestorm
int L;
for (int i = 0; i < Q; i++) {
cin >> L;
firestrom(1 << L);
}
for (int i = 0; i < board_size; i++) {
for (int j = 0; j < board_size; j++) {
sum += board[i][j];
}
}
// find maximum mTE
int maximum = 0;
for (int i = 0; i < board_size; i++) {
for (int j = 0; j < board_size; j++) {
if (!visited[i][j] && board[i][j] > 0) {
visited[i][j] = true;
maximum = max(maximum, 1 + dfs(i, j));
}
}
}
cout << sum << '\n'
<< maximum;
return 0;
}
여담
이번에는 뜬금없이 컴파일 에러를 한번 당했는데, 처음에 board_len변수를 size라 이름지었더니 그렇게 되었다. 내 설정에서는 문제 없었는데 왜 그러는지는 잘 모르겠지만, 일단은 vector나 deque 등의 stl에서 size가 사용되는 것 같다.
