<Baekjoon> #20058 Simulation, 구현 마법사 상어와 파이어스톰 c++

#20058 참고1 참고2

🧊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를 저장해주어 조사를 끝낸 후 마지막에 같이 녹여준다
• 얼음이 있는 칸 3개 이상과 인접해있지 않으면 녹기 때문에 현재 칸을 기준으로 상,하,좌,우를 탐색했을 때 얼음이 있는 칸이 3개 미만이면 체크를 해주고 녹인다

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

• 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 구해야 한다 (DFS/BFS 둘 다 가능)

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;
}