boj, 백준) 20058. 마법사 상어와 파이어스톰(C/C++)

1. 문제 링크

www.acmicpc.net/problem/20058

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

 

2. 문제 개요

크기가 2^N x 2^N인 격자로 나눠진 얼음판이 있다. A[r][c] (행 : r, 열 : c)의 값은 얼음의 양을 나타낸다.

파이어스톰을 시전하려면 시전 할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2^L x 2^L의 크기로 나누고 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸을 기준으로 3개 이상의 얼음과 인접해 있지 않으면 얼음의 양이 1 줄어든다.

 

파이어스톰을 q번 시전하고 난 뒤, 얼음판의 남아있는 얼음의 합, 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 구하는 프로그램을 작성해보자.

 

 

3. 문제 힌트

(1) 회전

   - 꼭 1개의 함수에 2^L x 2^L 크기의 격자를 모두 다 회전시켜야 할까.. 나눠서 할 수는 없을까?

 

(2) 인접 얼음 확인

   - '동시에' 이루어지기 때문에 값을 바로 적용해서는 안됨. 어딘가에 담아두자.

 

(3) 가장 큰 얼음 크기 구하기.

   - 단순히 BFS를 사용하면 된다. 얼음이 존재하는 부분만 따라서 탐색할 수 있도록 해주자.

 

위의 3가지만 하면 문제를 풀 수 있다.

 

4. 문제 풀이

문제를 읽고.. 또 회전하는 거 구현해야 한다는 생각에 풀고 싶지 않았지만.. 꽤나 단순하게 생각할 수 있으면서도 실수를 많이 하는 부분이기 때문에 했다. 실제로 시험장에서 회전 관련 나오면 멘붕에 빠지기 쉽다. 

 

우선, 회전을 어떻게 하면 간단하게 할 수 있을까? 를 생각해봤다.

회전하는 함수를 구현할 건데 만약 회전하려고 하는 격자의 크기가 4 x 4이라고 해보자. 그러면 4x4격자를 함수 1개에 모두 넣으면 구현이 상당히 복잡해진다. (끔찍)

 

그래서 밑의 코드에서 구현한 회전 함수는 4x4 격자에 대한 정보 (가장 왼쪽 위좌표, 한 변의 길이)를 넘겨주면 테두리만 회전하도록 했다. 

그 뒤, 호출할 때, 2x2 격자에 대한 정보를 넘겨주어서 내부도 회전할 수 있도록 했다. 문제를 쪼개는 방식으로...

 

얼음이 녹을 때는 동시에 이루어진다. 그래서 queue라던지, 또 다른 임시 배열을 만들어 줘서 값을 담아야 한다. 그렇게 하지 않고 바로바로 값을 바꿔버리면 안 녹아야 할 얼음이 녹을 수 있다. 

 

마지막 얼음 크기 구하는 것은 BFS를 사용해서 간단하게 구할 수 있다.

 

이 문제는 회전을 어떻게 간단하게 할 것인지.. 가 핵심인 문제인 것 같다.

(회전 <-> 녹이기) + 정답 구하기와 같은 간단한 흐름이지만 문제를 자세히 들여다보면 실수하기 딱 좋은 문제 유형

 

5. 코드

#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

int n, q, mapsize, sum_ans,num_ans;
int A[64][64];	//2^6
bool visited[64][64];


const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };

void rotateA(int y, int x, int len, int rotatedA[64][64])
{
	//[x, x+len-1]
	//[y, y+len-1]

	for (int j = x; j < x + len - 1; ++j)
		rotatedA[y + (j-x)][x + len - 1] = A[y][j];
	
	for (int i = y; i < y + len; ++i)
		rotatedA[y + len - 1][x + len - 1 - (i - y)] = A[i][x + len - 1];

	for (int j = x; j < x + len; ++j)
		rotatedA[y+(j-x)][x] = A[y+len-1][j];

	for (int i = y; i < y + len; ++i)
		rotatedA[y][x + len - 1 - (i - y)] = A[i][x];

	return;
}

void copy_map(int dest[64][64], int src[64][64])
{
	for (int i = 0; i < mapsize; ++i)
		for (int j = 0; j < mapsize; ++j)
			dest[i][j] = src[i][j];
	return;
}

int main()
{
	scanf("%d %d", &n, &q);

	mapsize = (int)pow(2, n);

	for (int i = 0; i < mapsize; ++i) 
		for (int j = 0; j < mapsize; ++j) 
			scanf("%d", &A[i][j]);
		
	
	for (int t = 0; t < q; ++t) {

		int l;
		scanf("%d", &l);

		int rotatedA[64][64] = { 0 };

		copy_map(rotatedA, A);
		
		int diff = (int)pow(2, l);

		for (int i = 0; i < mapsize; i+=diff) {
			for (int j = 0; j < mapsize; j+=diff) {
				
				int len = diff;
				int k = 0;
				while (len - 2*k > 1) {
					rotateA(i + k, j + k, len - 2*k, rotatedA);
					++k;
				}
			}
		}
		queue<int> qq;

		for (int cy = 0; cy < mapsize; ++cy) {
			for (int cx = 0; cx < mapsize; ++cx) {

				if (rotatedA[cy][cx] == 0)
				{
					qq.push(0);
				}
				else {
					int icenum = 0;

					for (int dir = 0; dir < 4; ++dir) {
						int nx = cx + dx[dir];
						int ny = cy + dy[dir];

						if (nx < 0 || ny < 0 || nx >= mapsize || ny >= mapsize || rotatedA[ny][nx] <= 0)
							continue;

						++icenum;
					}

					if (icenum < 3)
						qq.push(rotatedA[cy][cx] - 1);
					else
						qq.push(rotatedA[cy][cx]);
				}
			}
		}

		for (int i = 0; i < mapsize; ++i) 
			for (int j = 0; j < mapsize; ++j) {
				A[i][j] = qq.front(); 
				qq.pop();
			}
	}
	
	
	for (int i = 0; i < mapsize; ++i)
		for (int j = 0; j < mapsize; ++j) {
			sum_ans += A[i][j];
			if (!visited[i][j] && A[i][j] != 0) {

				queue<pair<int,int>> qq;
				int sum = 0, num = 0;

				visited[i][j] = true;
				qq.push({ i,j });

				while (!qq.empty()) 
				{
					pair<int, int> cur = qq.front(); qq.pop();
					++num;

					for (int dir = 0; dir < 4; ++dir) {
						int nx = cur.second + dx[dir];
						int ny = cur.first + dy[dir];

						if (nx < 0 || ny < 0 || nx >= mapsize || ny >= mapsize || visited[ny][nx] || A[ny][nx] == 0)
							continue;

						qq.push({ ny,nx });
						visited[ny][nx] = true;
					}
				}
				num_ans = max(num_ans, num);
			}
		}

	printf("%d\n%d", sum_ans, num_ans);

	return 0;
}

 

6. 결과