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

22.11.04. 다시 작성한 코드가 더 깔끔해서 갱신..

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

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

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
int N, Q;
int A[64 + 2][64 + 2];
int L[1000 + 2];

int M;
int tmp[64 + 2][64 + 2];

struct _st
{
	int x, y;
};
std::queue<_st> Ice;
int visited[64 + 2][64 + 2];
int total;

int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };


void debug()
{
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			printf("%d", A[i][j]);
		}
		printf("\n");
	}
}



void input()
{
	scanf("%d %d", &N, &Q);
	M = pow(2, N);
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &A[i][j]);
		}
	}
	for (int i = 0; i < Q; i++) {
		scanf("%d", &L[i]);
	}
}

void fire_storm(int len)
{
	memset(tmp, 0, sizeof(tmp));

	// rotate
	for (int x = 0; x < M; x += len) {			
		for (int y = 0; y < M; y += len) {	// 이때 만들어지는 (x, y)가 시작점이 된다. 
			for (int i = 0; i < len; i++) {
				for (int j = 0; j < len; j++) {
					tmp[x + i][y + j] = A[x + len - j - 1][y + i];
				}
			}
		}
	}
	memset(A, 0, sizeof(A));

	// search ice
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			if (tmp[i][j] == 0) continue;	// 얼음이 없는 칸은 탐색해줄 필요 없다 
			int ice = 0;
			for (int p = 0; p < 4; p++) {
				int nx = i + dir_x[p];
				int ny = j + dir_y[p];
				if (nx < 0 || nx > M - 1 || ny < 0 || ny > M - 1) continue;
				if (tmp[nx][ny] != 0) ice++;
			}
			if (ice < 3) A[i][j] -= 1;
		}
	}

	// del ice
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			A[i][j] += tmp[i][j];
		}
	}
}



void simul()
{
	for (int i = 0; i < Q; i++) {
		fire_storm(pow(2, L[i]));
	}
}


int BFS(int x, int y)
{
	Ice = {};

	Ice.push({ x, y });
	visited[x][y] = 1;
	int cnt = 1;
	total += A[x][y];

	while (!Ice.empty()) {
		_st data = Ice.front();
		Ice.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > M - 1 || ny < 0 || ny > M - 1) continue;
			if (A[nx][ny] == 0) continue;
			if (visited[nx][ny]) continue;
			cnt++;
			total += A[nx][ny];
			Ice.push({ nx, ny });
			visited[nx][ny] = 1;
		}
	}
	return cnt;
}



int output()
{
	int ice_berg = 0;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			if (visited[i][j]) continue;
			if (A[i][j] == 0) continue;
			int cnt = BFS(i, j);
			if (cnt == 1) continue;	// 덩어리가 안생김 // 격자 공간 하나의 값 
			if (ice_berg < cnt) ice_berg = cnt;
		}
	}
	return ice_berg;
}


int main()
{
	input();
	simul();
	printf("%d\n%d\n", total, output());
	return 0;
}

---

큐를 활용하여 rotate한 풀이는 아래와 같다. 

저 런타임에러 ? ㅋㅋ... 또 인덱스 실수 ^^ 개빡친다

#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>
int N, Q;
int M;	// 맵 크기
int A[64 + 2][64 + 2];	// 원본 맵 
int S[64 + 2][64 + 2];	// 복사 진행할 맵
int L[1000 + 2];
int visited[64 + 2][64 + 2];

struct _st
{
	int x, y;
};


int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };


void input()
{
	scanf("%d %d", &N, &Q);
	M = pow(2, N);
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &A[i][j]);
		}
	}
	for (int i = 0; i < Q; i++) {
		scanf("%d", &L[i]);
	}
}


void rotate_ice(int x, int y, int m)
{
	std::queue<int> B;
	int col = y;
	for (int i = x + m - 1; i >= x; i--) {
		for (int j = y + m - 1; j >= y; j--) {
			B.push(A[i][j]);
		}
		for (int k = x + m - 1; k >= x; k--) {
			S[k][col] = B.front();
			B.pop();
		}
		col++;
	}
}



void move_ice(int level)
{
	std::fill(&S[0][0], &S[0][0] + sizeof(S) / sizeof(int), 0);
	int m = pow(2, level);
	for (int i = 0; i < M; i += m) {
		for (int j = 0; j < M; j += m) {
			rotate_ice(i, j, m);
		}
	}
}



void del_ice()
{
	std::fill(&A[0][0], &A[0][0] + sizeof(A) / sizeof(int), 0);
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			if (S[i][j] == 0) continue;
			int cnt = 0;
			for (int p = 0; p < 4; p++) {
				int ni = i + dir_x[p];
				int nj = j + dir_y[p];

				if (ni < 0 || ni > M || nj < 0 || nj > M) continue;
				if (S[ni][nj] == 0) continue;
				if (S[ni][nj]) cnt++;
			}
			if (cnt < 3) A[i][j] = S[i][j] - 1;
			else A[i][j] = S[i][j];
		}
	}
}




void simul()
{
	for (int i = 0; i < Q; i++) {
		move_ice(L[i]);
		del_ice();
	}
}


int sum_ice()
{
	int total = 0;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			if (A[i][j] == 0) continue;
			total += A[i][j];
		}
	}
	return total;
}




int BFS(int x, int y)
{
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
	std::queue<_st> Que;
	Que.push({ x, y});
	visited[x][y] = 1;
	int cnt = 1;	// 자기자신

	while (!Que.empty()) {
		_st data = Que.front();
		Que.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > M || ny < 0 || ny > M) continue;
			if (A[nx][ny] == 0) continue;
			if (visited[nx][ny]) continue;
			Que.push({ nx, ny});
			visited[nx][ny] = 1;
			cnt += 1;
		}
	}
	return cnt;
}


int max_ice()
{
	int ans = 0;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			if (A[i][j] == 0) continue;
			int tmp = BFS(i, j);
			ans = (tmp > ans) ? tmp : ans;
		}
	}
	if (ans == 1) return 0;
	return ans;
}



int main()
{
	input();
	simul();
	int total = sum_ice();
	int iceberg = max_ice();
	printf("%d\n%d\n", total, iceberg);
	return 0;
}

아 ~~ 인덱스 실수 하지말라고 ~~~ 파이어스톰을 총 Q번 실행할 수 있는데 Q는 1000까지라잖아 ~~~~ 개바보야 ~~~ OOB 두개는 인덱스 100까지 줘서.... ㅋㅎ..

 

 

// rotate_ice( ) 함수

이거 그냥 90도 회전하는 코드로 구현하려고 했는데 그렇게 하면 source맵이랑 destination맵이랑 인덱스가 안맞아서 회전이 잘 안된다. (일단 나는 실패하긴 했는데 하신 분이 있을수도...) 그래서 나는 source맵에서 가장 마지막 행부터 첫번째 행 까지 탐색하는데, 열번호가 큰 것 부터 큐 B에 담고 이것을 destination 맵에서 열번호가 작은 것 부터 큰 것까지 옮겨주었다.

// source 맵
1  2  3  4 
9  10 11 12 
17 18 19 20
25 26 27 28  > 가장 마지막 행의 마지막 열부터 (28, 27, 26, 25) 빼고 


// destination 맵
25
26
27
28
^
가장 첫행의 
마지막 열부터 (28, 27, 26, 25)
넣음

// del_ice( ) 함수

"얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸" 이라고 했으므로, 특정 칸 (i, j)가 영역 외부와 인접해있는 경우 얼음이 없는 칸과 인접해 있다고 생각해야한다. 이 부분을 간과해서 디버깅하느라고 30분 이상 씀... ..... 역시 문제가 하라는 대로 해야한다... 킁스..