[C++]백준20058번 마법사 상어와 파이어스톰

문제는 다음과 같다.

오늘은 백준20058번 마법사 상어와 파이어스톰 문제를 풀어보도록 하자. 작년 하반기 S전자 기출문제로 역시 시뮬레이션 문제이다. 이번 문제를 풀면서 얻은 것이 있다. 바로 pow()함수 를 쓰지말자.

pow()함수 를 쓰는건 나쁘지 않다. 하지만 무분별한 pow함수 때문에 TLE 에 걸려버렸다. 이유를 알 수 없었다. pow함수가 의심쩍어 시간복잡도를 확인해보니 O(N)인걸 확인하고 기겁을 했다. 이렇게 큰 함수를 아무 생각없이 쓰고 있었다는 것에 비통함을 금치못했다.

그래서 Bitmasking을 쓰기로 했다. 문제를 보면 2의 n승수만큼 자르기 때문에 N = 1«N; 이런 식으로 Bitmasking을 해서 고정 값을 만들고 for문에 적용했다.

TLE 가 난 코드를 보면.. for(int i=0;i<pow(2,N);i++)에 또 for문을 곁들인.. 매우 비참한 코드였다. 만일 N이 8이라면 64번을 또 곱하는 불상사가 발생한다.

따라서 pow(2,N)을 고정 값으로 설정하던지, Bitmasking한 값을 고정 값으로 설정하고 풀어야 했다. 문제는 구현, BFS라 그리 복잡하지 않았다. 내가 문제를 풀면서 얻어가는게 있다는 것에 만족한다.

                                     [코드]
/*
1. 격자L를 나눈다.
2. 2^L x 2^L만큼의 배열을 시계방향으로 90도 회전
3. 얼음이 있는 칸 3개가 없으면 얼음의 양이 1 줄어든다.

answer : 남아있는 얼음의 합 ,
		 남아있는 가장 큰 덩어리가 차지하는 칸의 갯수
		 
*/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct pos {
	int y;
	int x;
};

int map[64][64];//맵
int temp_location[64][64];//격자 나누고 맵에 넣어줄 것
bool visit[64][64];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int N, Q, level, first_answer = 0, second_answer = 0;//맵 크기=2^N, Q=격자 쪼갤 횟수,level=쪼개는 크기

bool Inbound(int y, int x) {
	return y >= 0 && x >= 0 && y < N && x < N;
}

void mass_cnt(int a, int b) {
	queue<pos>mass_Q;
	int cnt = 1;
	visit[a][b] = true;
	mass_Q.push({ a,b });

	while (!mass_Q.empty()) {
		int y = mass_Q.front().y;
		int x = mass_Q.front().x;

		mass_Q.pop();

		for (int i = 0; i < 4; i++) {
			int my = y + dir[i][0];
			int mx = x + dir[i][1];

			if (Inbound(my,mx)) {
				if (map[my][mx] > 0 && !visit[my][mx]) {
					visit[my][mx] = true;
					cnt++;
					mass_Q.push({ my,mx });
				}
			}
		}
	}
	if (second_answer < cnt)second_answer = cnt;
}

void melting(int N) {
	queue<pos>Q;
	vector<pos>V;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] > 0) {//얼음있으면 큐에 넣기
				Q.push({ i,j });
			}
		}
	}

	while (!Q.empty()) {
		int y = Q.front().y;
		int x = Q.front().x;
		int cnt = 4;
		Q.pop();

		for (int i = 0; i < 4; i++) {
			int my = y + dir[i][0];
			int mx = x + dir[i][1];

			if (!Inbound(my,mx)) {
				cnt--;
				continue;
			}
			if (map[my][mx] <= 0) {
				cnt--;
			}
		}
		if (cnt < 3) {
			V.push_back({ y,x });
		}
	}

	for (int i = 0; i < V.size(); i++) {
		map[V[i].y][V[i].x]--;
	}
}

void clock_lotate(int y, int x, int M) {//기준점과 쪼개는 크기
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			temp_location[j][M - 1 - i] = map[y+i][x+j];
		}
	}

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			map[y+i][x+j] = temp_location[i][j];
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> Q;
	N = 1 << N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < Q; i++) {
		cin >> level;
		int M = 1 << level;
		if (level > 0) {
			for (int i = 0; i < N; i += M) { //회전
				for (int j = 0; j < N; j += M) {
					clock_lotate(i, j, M);
				}
			}
		}
		melting(N);
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] > 0) {
				first_answer += map[i][j];//1번정답
			}
		}
	}
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] != 0 && !visit[i][j]) {
				mass_cnt(i, j);//2번정답
			}
		}
	}

	cout << first_answer<<'\n';
	cout << second_answer;
}