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

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

www.acmicpc.net/problem/20058

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

---

/* 문제 설명 */

2N × 2N 격자의 얼음판을 2L × 2L 크기의 부분 격자로 나눈다.

그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다.

이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸의 얼음을 -1 해준다.

위의 행동을 Q번 할 때, 모든 파이어스톰을 시전한 후에 남아있는 얼음 A[r][c]의 합과 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 구하시오.

 

/* 해결 방안 */

1. 부분 격자를 시계 방향으로 돌려주기.

2. 주변에 얼음이 2개 이상 없는 애들 -1 해주기.

3. 마지막으로  탐색을 통해서 가장 큰 덩어리와 얼음의 합 구해주기.

 

우선 이 문제를 풀기 위해서는 배열을 쪼개는 방법을 알아야합니다. (분할정복)

 

 

함수 func(int sx, int dx, int sy, int dy, ... , ...)는 (sx, sy)부터 (dx,dy)까지의 부분 격자를 돌려주는 역할을 합니다.

여기서 func(좌측sx, 우측sy, 상단dx, 하단dy)이라고 합시다.

편의상 dx, dy라고 적었지만, dx는 sx+d(변의 길이)이고, dy는 sy+d입니다. 

중요한 점인데, 분할로 쪼갠다는 것은 현재의 변의 길이를 반으로 줄여나간다는 뜻입니다.

즉, sx, sy, sx+d, dy+d 였다면, 다음 차례에선 sx, sy, sx+(d/2), dy+(d/2) 이렇게 된다는 거죠.

강조한 이유는 이따가 나옵니다!

 

 

우선, 함수의 동작부터 봅시다.

처음은 func(0, N, 0, N)에서 시작합니다. N×N을 4분할로 쪼갭시다!

그러면 L = 2처럼 나뉘게 됩니다. 여기에 번호를 붙여보고 함수의 수행 과정을 살펴보죠.

 

1	2
3	4

 

1번 : func(0, N/2, 0, N/2)

2번 : func(0, N/2, N/2, N)

3번 : func(N/2, N, 0, N/2)

3번 : func(N/2, N, N/2, N)

 

그럼 이렇게 됩니다.

 

 

감을 잡기 위해, 이걸 또 분할해봅시다. 그러면 L = 1처럼 나뉘게 됩니다.

가장 왼쪽에 있는 부분 격자를 살펴본다면,

 

1번 : func(0, N/4, 0, N/4)

2번 : func(0, N/4, N/4, N/2)

3번 : func(N/4, N/2, 0, N/4)

3번 : func(N/4, N/2, N/4, N/2)

 

이렇게 됩니다.

 

 

즉, 부분격자의 전체 크기가 쿼리로 주어지는 L과 같아질 때까지, 변의 길이를 반씩 줄여가면 됩니다.

 

 

여기서 주의할 것이 있다면, 단순하게 좌표에다가 / 2 를 수행하면 안된다는 점입니다. 

 

예를 들어, func(0, 4, 4, 8)에 대해 좌표에다가 2를 나누게 되면,

1번 : func(sx, dx/2, sy, dy/2)  →  func(0, 2, 4, 4)   →  ??????????? 

2번 : func(sx, dx/2, dy/2, dy)

3번 : func(dx/2, dx, sy, dy/2)

3번 : func(dx/2, dx,  dy/2, dy)

 

좌표값이 이상해집니다!

당연한 소리겠지만, dx = sx+d(변의 길이)이기 때문입니다.

현재 우리는 변의 길이를 반 씩 줄여가며 dx를 좌표를 찾아내고 있는거지, dx를 반으로 나누는게 아닙니다!

 

 

그러면, 이제 격자를 잘 나눠주었으니 배열을 돌립니다.

이건 아래 코드를 보시면 됩니다.

 

 

드디어 배열을 돌리는 게 끝이 났습니다.

그러면 이제 이중 for문을 각 좌표에 방문하고, 주변에 얼음이 몇 개 있나 카운팅해준뒤 얼음이 녹는 걸 처리해줍니다.

 

 

1번과 2번을 Q번 반복하고, 남은 얼음의 양과 가장 큰 얼음 덩어리의 크기를 구하기 위해 BFS를 수행합니다.

 

/* 구현 과정 */

1. 부분격자를 회전시켜주는 함수 func( )을 호출합니다.

2. 이후, 얼음을 녹여주는 melt( )를 호출합니다.

3. 1번과 2번을 Q번 반복 후, bfs를 통해 답을 구해줍니다.

 

/* 소스 코드 */

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define mod 10007
typedef long long ll;
typedef pair<int, int>pi;
typedef pair<pi, int>pii;

int n, N, arr[80][80], q, L, ans1, ans2;
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
bool visited[80][80];
vector<int>query;

bool outrange(int x, int y) {
	if (x < 0 || y < 0 || x >= N || y >= N) return 1;
	return 0;
}

void func(int sx, int dx, int sy, int dy, int step, int goal) {
	if (step == goal) {
		//rotate
		int tmp[80][80] = { 0, };
		for (int i = sx, y = dy - 1; i < dx; i++, y--) {
			for (int j = sy, x = sx; j < dy; j++, x++) {
				tmp[x][y] = arr[i][j];
			}
		}
		for (int i = sx; i < dx; i++)
			for (int j = sy; j < dy; j++)
				arr[i][j] = tmp[i][j];
		return;
	}

	int diff = 1 << (step - 1);
	func(sx, sx + diff, sy, sy + diff, step - 1, goal);
	func(sx, sx + diff, sy + diff, dy, step - 1, goal);
	func(sx + diff, dx, sy, sy + diff, step - 1, goal);
	func(sx + diff, dx, sy + diff, dy, step - 1, goal);
}

void melt() {
	vector<pi>ice;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (arr[i][j] == 0)  continue;
			int flag = 0;
			for (int k = 0; k < 4; k++)
			{
				int x = i + dx[k];
				int y = j + dy[k];
				if (outrange(x, y)) {
					flag++; continue;
				}
				if (arr[x][y] == 0) flag++;
			}
			if (flag > 1) ice.push_back({ i,j });
		}
	}

	for (int i = 0; i < ice.size(); i++)
	{
		int x = ice[i].first;
		int y = ice[i].second;
		arr[x][y] = max(0, arr[x][y] - 1);
	}
}

void bfs(int ssx, int ssy) {
	queue<pi>q;

	q.push({ ssx,ssy});
	visited[ssx][ssy] = 1;
	ans1 += arr[ssx][ssy];
	int cnt = 1;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (outrange(nx, ny)) continue;
			if (visited[nx][ny]) continue;
			if (arr[nx][ny] == 0) continue;

			visited[nx][ny] = 1;
			ans1 += arr[nx][ny]; cnt++;
			q.push({ nx,ny });
		}
	}
	ans2 = max(ans2, cnt);
}

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

	cin >> n >> q;
	N = 1 << n;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> arr[i][j];

	while (q--) {
		int l; cin >> l;
		func(0, N, 0, N, n, l);
		melt();
	}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (arr[i][j] != 0 && !visited[i][j]) bfs(i, j);

	cout << ans1 << "\n" << ans2;
}

/* 얻어갈 점 */

1. 부분 격자를 살펴볼 때, 좌표 계산을 정확하게 하자. 단순히 좌표를 / 2 하는 것이 아니라, 변의 길이에 대해서 / 2 하는 것이다.

2. sx, dx, sy, dy에서 dx = sx+변의 길이다.

3. 배열을 돌려줄 때, 굳이 tmp[ ][ ]을 만드는 것 대신, vector를 이용해서 차례대로 넣어주는 방법도 있다.

 

 

---