🧊Solution & Idea
2^L*2^L
인 부분으로 나누어 시계 방향으로 90도로 회전하는 부분, 얼음의 양을 줄이는 부분, 가장 큰 덩어리를 찾는 부분으로 나눈다>>
은 2의 거듭제곱으로 나누기, <<
은 2의 거듭제곱을 곱할 때 사용한다🧊Rotate
먼저 돌아가는 모양을 생각해본다. 다음과 같이 길이(Len)
가 4
인 경우 돌아가고 난 후 각 맵에 있는 값의 변화를 살펴본다
크게 2개
사각형 둘레(?)의 회전으로 나눌 수 있다.
따라서 돌려야 하는 갯수는 int square=2/Len
임을 알 수 있다.
각 사각형마다 기준점의 좌표를 생각해본다
이해가 안 된다면 (8x8)
의 경우를 천천히 생각해보자
실제로 한 줄씩 시계방향으로 이동한다
시작점 (1,1)
을 (Sy, Sx)
라 두고, 끝점 (4,4)
를 (Ey, Ex)
라 두었을 때 각 부분의 범위를 설정해보면
A: (Sy, Sx)~(Ey-1, Sx)
B: (Ey, Sx)~(Ey, Ex-1)
C: (Ey, Ex)~(Sy+1, Ex)
D: (Sy, Sx+1)~(Sy, Ex)
와 같이 나타낼 수 있고 코드 상으로는 다음과 같이 나타낼 수 있다
int y = endY; int x = startX; int idx = 0;
vector<int> tmp;
for (int i = startY; i < endY; i++) tmp.push_back(map[i][startX]);
for (int i = startY; i < endY; i++) map[i][startX] = map[endY][x++];
for (int i = startX; i < endX; i++) map[endY][i] = map[y--][endX];
for (int i = endY; i > startY; i--) map[i][endX] = map[startY][x--];
for (int i = endX; i > startX; i--) map[startY][i] = tmp[idx++];
** 참고로 Rotate 함수를 구현할 때 다음과 같이 간단하게 구현할 수 있지만 이 과정이 명확하게 잘 이해가 되지는 않아 위에처럼 길게 풀이한 풀이를 찾았다
L=(1<<L);
// 모든 격자에 대한 회전
for(int i=0;i<N;i+=L)
for(int j=0;j<N;j+=L)
rotate(i,j,L);
void rotate(int y, int x, int L){
for(int i=0;i<L;i++)
for(int j=0;j<L;j++)
temp[i][j]=board[y+L-1-j][x+i];
for(int i=0;i<L;i++)
for(int j=0;j<L;j++)
board[y+i][x+j]=temp[i][j];
}
🧊Melting Ice
bool checkMelt[MAX][MAX]
를 만들어 현재 조사했던 칸이 녹을 예정인 칸이면 ture
를 저장해주어 조사를 끝낸 후 마지막에 같이 녹여준다void melting_ice() {
memset(checkMelt, false, sizeof(checkMelt));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 0) continue;
int cnt = 0;
for (int d = 0; d < 4; d++) {
int ny = i + dy[d];
int nx = j + dx[d];
if (ny < 0 || nx<0 || ny >= N || nx>+N) continue;
if (map[ny][nx] > 0) cnt++;
}
if (cnt < 3) checkMelt[i][j] = true;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (checkMelt[i][j]) {
map[i][j]--;
}
}
}
}
🧊Get Biggest
1. DFS
int dfs(int y, int x) {
visited[y][x] = true;
int ret = 1;
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
if (!visited[ny][nx] && map[ny][nx] > 0)
ret += dfs(ny, nx);
}
return ret;
}
int get_biggest() {
int ret = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] > 0 && !visited[i][j])
ret = max(ret, dfs(i, j));
}
}
return ret;
}
2. BFS
int bfs(int y, int x) {
queue<pair<int, int>> q;
q.push({ y,x });
visited[y][x] = true;
int cnt = 1;
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
if (!visited[ny][nx] && map[ny][nx] > 0) {
visited[ny][nx] = true;
q.push({ ny, nx });
cnt++;
}
}
}
return cnt;
}
int get_biggest2() {
int ret = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] > 0 && !visited[i][j])
ret = max(ret, bfs(i, j));
}
}
return ret;
}
🧊Source Code
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
const int MAX = 64;
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
int N, Q;
vector<vector<int>> map;
bool checkMelt[MAX][MAX], visited[MAX][MAX];
int bfs(int y, int x) {
queue<pair<int, int>> q;
q.push({ y,x });
visited[y][x] = true;
int cnt = 1;
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
if (!visited[ny][nx] && map[ny][nx] > 0) {
visited[ny][nx] = true;
q.push({ ny, nx });
cnt++;
}
}
}
return cnt;
}
int get_biggest2() {
int ret = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] > 0 && !visited[i][j])
ret = max(ret, bfs(i, j));
}
}
return ret;
}
int dfs(int y, int x) {
visited[y][x] = true;
int ret = 1;
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
if (!visited[ny][nx] && map[ny][nx] > 0)
ret += dfs(ny, nx);
}
return ret;
}
int get_biggest() {
int ret = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] > 0 && !visited[i][j])
ret = max(ret, dfs(i, j));
}
}
return ret;
}
int get_sum() {
int ret = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
ret += map[i][j];
return ret;
}
void melting_ice() {
memset(checkMelt, false, sizeof(checkMelt));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 0) continue;
int cnt = 0;
for (int d = 0; d < 4; d++) {
int ny = i + dy[d];
int nx = j + dx[d];
if (ny < 0 || nx<0 || ny >= N || nx>+N) continue;
if (map[ny][nx] > 0) cnt++;
}
if (cnt < 3) checkMelt[i][j] = true;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (checkMelt[i][j]) {
map[i][j]--;
}
}
}
}
void rotate(int r, int c, int len) {
int square = len / 2; //각각 내접하는 사각형 갯수
for (int number = 0; number < square; number++) {
int startY = r + number;
int startX = c + number;
int endY = r + len - number - 1;
int endX = c + len - number - 1;
int y = endY; int x = startX; int idx = 0;
vector<int> tmp;
for (int i = startY; i < endY; i++) tmp.push_back(map[i][startX]);
for (int i = startY; i < endY; i++) map[i][startX] = map[endY][x++];
for (int i = startX; i < endX; i++) map[endY][i] = map[y--][endX];
for (int i = endY; i > startY; i--) map[i][endX] = map[startY][x--];
for (int i = endX; i > startX; i--) map[startY][i] = tmp[idx++];
}
}
void solution() {
while (Q--) {
int L; cin >> L;
L = (1 << L);
for (int i = 0; i < N; i += L)
for (int j = 0; j < N; j += L)
rotate(i, j, L);
melting_ice();
}
cout << get_sum() << endl;
cout << get_biggest() << endl;
}
void input() {
cin >> N >> Q;
N = (1 << N); //2의 거듭제곱 곱하기
map = vector<vector<int>>(N+1, vector<int>(N+1));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solution();
return 0;
}