[백준] 마법사 상어와 파이어스톰

문제 설명

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

제한사항

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

---

풀이

50분
작년 하반기 공채 시험장에서 풀어본 문제이다. 당시 시간이 부족해서 완전히 풀이하지 못했던 기억이 난다. 한 번 이해했었던 문제여서인지, 집에서 편하게 풀어서인지 모르겠지만 생각보다 빠르게 풀어냈다. 다만 2차원 배열을 나누어 시계 방향으로 돌리는 식을 처음에 잘못 작성한 것에서 시간을 가장 많이 썼다.

// temp[sj + j][si + rotate_size - 1 - i] = board[si + i][sj + j];
temp[si + j][sj + rotate_size - 1 - i] = board[si + i][sj + j];

코드

// 09:52 ~ 10:43
// #pragma warning (disable:4996)
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>

using namespace std;

int board[64][64] = { 0, };
int n, q, lv, board_size;

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

void rotate(int lv) {
	int temp[64][64] = { 0, };
	int rotate_size = pow(2, lv);

	for (int si = 0; si < board_size; si += rotate_size) {
		for (int sj = 0; sj < board_size; sj += rotate_size) {
			for (int i = 0; i < rotate_size; ++i) {
				for (int j = 0; j < rotate_size; ++j) {
					temp[si + j][sj + rotate_size - 1 - i] = board[si + i][sj + j];
				}
			}
		}
	}

	for (int i = 0; i < board_size; ++i) {
		for (int j = 0; j < board_size; ++j) {
			board[i][j] = temp[i][j];
		}
	}

}

void melt() {
	int adj[64][64] = { 0, };
	for (int i = 0; i < board_size; ++i) {
		for (int j = 0; j < board_size; ++j) {
			for (int d = 0; d < 4; ++d) {
				if (i + dx[d] < 0 || j + dy[d] < 0 || i + dx[d] >= board_size || j + dy[d] >= board_size) continue;
				if (board[i + dx[d]][j + dy[d]] > 0) ++adj[i][j];
			}
		}
	}

	for (int i = 0; i < board_size; ++i) {
		for (int j = 0; j < board_size; ++j) {
			if (adj[i][j] < 3 && board[i][j] > 0) --board[i][j];
		}
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);

	cin >> n >> q;
	board_size = pow(2, n);
	for (int i = 0; i < board_size; ++i) {
		for (int j = 0; j < board_size; ++j) {
			cin >> board[i][j];
		}
	}

	while (q > 0) {
		cin >> lv;

		if(lv != 0) rotate(lv);

		melt();
		
		--q;
	}

	int sum = 0, max_ice = 0, local_ice;
	int visit[64][64] = { 0, };
	queue<pair<int, int>> q;
	
	for (int i = 0; i < board_size; ++i) {
		for (int j = 0; j < board_size; ++j) {
			if (visit[i][j] == 0 && board[i][j] > 0) {
				visit[i][j] = 1;
				q.push({ i,j });
				local_ice = 0;
				while (!q.empty()) {
					++local_ice;
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					sum += board[x][y];
					for (int d = 0; d < 4; ++d) {
						int nx = x + dx[d];
						int ny = y + dy[d];
						if (nx < 0 ||ny < 0 ||nx >= board_size || ny >= board_size) continue;
						if (visit[nx][ny] == 0 && board[nx][ny] > 0) {
							visit[nx][ny] = 1;
							q.push({ nx,ny });
						}
					}
				}
				if (local_ice > max_ice) max_ice = local_ice;
			}
		}
	}
	
	cout << sum << endl << max_ice;

	return 0;
}