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

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

20058번: 마법사 상어와 파이어스톰

 

- 구현 + 약간의 BFS가 섞인 문제이다. 시간복잡도는 모든 칸에 대해 회전을 진행하므로 N^2 * Q = O(QN^2)이다. 

 

- 먼저, 회전을 진행 할 구역의 길이 area_length(2^l)를 구한다. cmath 헤더의 pow 메서드를 사용하면 제곱수를 간단하게 구할 수 있다. 이 후, 이 값을 활용 해 주면서 start_x, start_y 좌표를 갱신하면서 해당 구역의 회전을 시작한다.

 

- 회전의 경우, 필자는 겉 테두리 부터 한 칸씩 좁혀들어가면서 회전을 하도록 구현했다. 벡터 4개를 선언하고, 각각 윗변, 오른쪽 변, 아랫쪽 변, 왼쪽 변의 값들을 담아준다. 이 후, 순서대로 오른쪽 변, 아랫쪽 변, 왼쪽 변, 윗 변에 해당 좌표들을 담아준다. 이 때, push_back을 해 주는 순서를 잘 고려해서 담아주어야 한다. 디버깅으로 지속해서 확인하는 것도 필수. 이 후 하나의 테두리가 끝났다면 start좌표 x와 y를 각각 +1 해주고, area_length도 2*k를 빼 준 상태로 다음 안쪽 테두리 회전을 진행한다.

 

- 다음으로, minus_ice 메서드를 통해, 인접한 칸 중 얼음이 있는 칸이 3개 이상인지를 체크하였다. 이 과정에서 4개의 구석 칸은 반드시 얼음이 1씩 감소하게 된다. will_minus에 감소 여부를 true로 체크 해 준 후, 다음 이중 for문에서 이에 맞게 감소시켰다. 왜냐하면, 한 칸마다 감소 여부와 감소를 연이어서 진행하는 경우 실제 목표값과 일치하지 않는 문제가 생긴다.

 

- 모든 마법을 마쳤다면, 칸의 얼음 수를 더하면서 동시에 BFS를 진행한다. BFS는 간단하게 인접한 area 덩어리들 중에서 가장 많은 칸의 갯수를 구하면 된다. 20줄 내로 끝낼 수 있다.

 

- 시간을 좀 많이 사용했는데, 나눠진 구역들을 90도 회전을 하는 부분을 다르게 구현 해 보고 싶어서, 구역을 1/4로 나누고 각 칸들을 시계방향으로 이동시키는 방법을 사용해서였다. 사실 문제를 잘못 읽었다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;

int n, q, l, big_area;
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
int map[64][64];
bool visited[64][64], will_minus[64][64];

void debugging() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << map[i][j]<< ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}

bool minus_ice(int x, int y) {
	int ice_area = 0;
	for (int k = 0; k < 4; k++) {
		int nx = x + dx[k]; int ny = y + dy[k];
		if (nx < 0 || nx >= n || ny < 0 || ny >= n || !map[nx][ny]) continue;
		ice_area++;
	}
	if (ice_area >= 3) return false;
	return true;
}

void bfs(int x, int y) {
	int temp_sum = 1;
	queue<pair<int,int>> q;
	visited[x][y] = true;
	q.push({ x,y });
	while (!q.empty()) {
		int tx = q.front().first;
		int ty = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int nx = tx + dx[k];
			int ny = ty + dy[k];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (visited[nx][ny] || !map[nx][ny]) continue;
			visited[nx][ny] = true;
			temp_sum++;
			q.push({ nx,ny });
		}
	}
	big_area = max(big_area, temp_sum);
}

int main() {
	cin >> n >> q;
	n = pow(2, n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	while (q--) {
		cin >> l;
		int area_length = pow(2, l);
		for (int i = 0; i < n; i += area_length) {
			for (int j = 0; j < n; j += area_length) {
				int now_x, now_y; int k = 0; int temp_area_length = area_length;
				while (k < area_length / 2) {
					now_x = i + k; now_y = j + k; temp_area_length = area_length - 2 * k;
					vector<int> temp[4];
					int m = 0; 
					for (int o = 0; o < temp_area_length; o++) temp[m].push_back(map[now_x][now_y +o]); //윗 변
					m++; now_y += (temp_area_length-1);
					for (int o = 0; o < temp_area_length; o++) temp[m].push_back(map[now_x+o][now_y]); // 오른쪽 변 (위부터 아래로)
					m++; now_x += (temp_area_length - 1);
					for (int o = 0; o < temp_area_length; o++) temp[m].push_back(map[now_x][now_y - o]);//아랫변(오른쪽부터 왼쪽으로)
					m++; now_y -= (temp_area_length - 1);
					for (int o = 0; o < temp_area_length; o++) temp[m].push_back(map[now_x - o][now_y]); // 왼 변(아래부터 위로)
					now_x = i + k; now_y = j + k + (temp_area_length - 1); m = 0;
					for (int o = 0; o < temp_area_length; o++) map[now_x + o][now_y] = temp[m][o];
					m++; now_x += (temp_area_length - 1);
					for (int o = 0; o < temp_area_length; o++) map[now_x][now_y -o] = temp[m][o];
					m++; now_y -= (temp_area_length - 1);
					for (int o = 0; o < temp_area_length; o++) map[now_x - o][now_y] = temp[m][o];
					m++; now_x -= (temp_area_length - 1);
					for (int o = 0; o < temp_area_length; o++) map[now_x][now_y+o] = temp[m][o];
					k++;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (minus_ice(i, j)) will_minus[i][j] = true;
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!map[i][j]) continue;
				if (will_minus[i][j]) map[i][j]--;
			}
		}
		memset(will_minus, false, sizeof(will_minus));
	}
	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sum += map[i][j];
			if (visited[i][j] || !map[i][j]) continue;
			bfs(i, j);
		}
	}
	cout << sum << '\n' << big_area;
	return 0;
}