[BOJ] 20058 : 마법사 상어와 파이어스톰 (C++)

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

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

걸린 시간 : 59분 47초

---

소문제 3개 정도로 쪼갤 수 있는 구현 문제이다. 항상 구현에서 힘들었는데 이 문제를 비교적 쉽게 해결한 것 같아 마음이 놓인다...

알고리즘

소문제는 다음과 같이 나눌 수 있을 것이다.

1. L 값에 따라 배열을 회전
2. 회전한 후 3칸 이상의 얼음과 인접하지 않은 칸은 얼음의 양 감소
3. 모든 마법이 끝나고 얼음의 총량과 연결 요소의 최대 크기 파악

하나하나 차근차근 해보자.

1. L 값에 따라 배열을 회전

• 코드에서의 magic() 함수이다. 파라미터로 L 값을 전달한다.
• magic 함수는 전체 배열을 회전하는 함수이고, 그 안에서 조그만 조각들을 직접 회전하는 함수를 rot() 로 다시 호출한다.
• rot() 함수에는 파라미터가 해당 조각의 시작점 i, 시작점 j, 조각의 크기 piece를 전달한다. 조각을 특정하려면 3개의 변수가 필요하다는 것이 중요하다.
• 돌리는 과정에서 실제 배열 말고 돌려놓은 결과를 임시 저장할 배열이 필요하다. tmp 라는 이름으로 배열을 사용한다.
• 배열을 돌리는 것은 다음과 같은 식으로 쓸 수 있다.

tmp[si+j][sj+piece-1-i] = board[si+i][sj+j];

이 그림을 보면 이해가 잘 될 것이다. 직접 하나하나 생각해보면서 이 식을 생각할 수 있어야 한다. 이 문제의 핵심이었던 것 같다.

2. 회전한 후 3칸 이상의 얼음과 인접하지 않은 칸은 얼음의 양 감소

• 배열의 값 하나하나 살펴보면서 주변에 얼음이 3칸 이상 없는 칸을 찾아 얼음을 감소시키면 된다. 간단하다.
• 처음엔 모든 칸에 얼음이 들어있으면 주변에 얼음이 계속 존재할텐데 어떻게 얼음의 양이 감소하지...? 생각했는데, 꼭짓점 부분은 얼음이 주변에 최대 2칸 있으므로 무조건 얼음의 양이 감소한다는 걸 깨달았다.
• 주의할 점은, 직접 사용하는 배열인 board를 사용하면 안된다. 얼음의 양이 감소되는 것은 동시에 일어나는 일이므로 차례차례 board배열로 확인하면서 board배열을 동시에 변경하면 안된다. 만약 얼음의 양을 감소시켰다면 다음 차례의 값들은 "감소된 양"을 보고 판단하게 된다.
  따라서, 아까 회전할 때 썼던 tmp 배열이 board 배열과 똑같은 상태임을 떠올려서 tmp 배열로 확인하고 board 배열을 변경하면 된다.

3. 모든 마법이 끝나고 얼음의 총량과 연결 요소의 최대 크기 파악

• 이 부분을 거치면 문제의 모든 부분이 끝난다. 이런 경우엔 연결 요소를 파악할 때 파괴적인 코드를 작성해도 된다. 연결되어 있는 것을 확인하면서 해당 자리의 값을 0으로 만드는 것이다.
  https://morenow.tistory.com/26 이 문제에서도 연결 요소만 파악하는 문제이므로 파괴적인 코드를 작성한 바 있다.
• 해당 자리의 값을 0으로 만들기 전에 total 이라는 변수에 해당 값을 더해주면 얼음의 총량이 나오게 된다. 이렇게 연결 요소를 파악하면서 얼음의 총량을 계산하면 따로 배열을 탐색하며 얼음의 총량을 계산하지 않아도 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int board[70][70];
int tmp[70][70];
int N, Q, L[1001], boardsize, mx, total;
int di[4] = {-1, 0, 1, 0};
int dj[4] = {0, 1, 0, -1};

void rot(int si, int sj, int piece) {
	for (int i = 0; i < piece; i++) {
		for (int j = 0; j < piece; j++) {
			tmp[si+j][sj+piece-1-i] = board[si+i][sj+j];
		}
	}
}

void magic(int l) {
	int piece = pow(2, l);
	for (int i = 0; i < boardsize; i += piece) {
		for (int j = 0; j < boardsize; j+= piece) {
			rot(i, j, piece);
		}
	}
	for (int i = 0; i < boardsize; i++) {
		for (int j = 0; j < boardsize; j++) {
			board[i][j] = tmp[i][j];
		}
	}
}

int conn (int ci, int cj) {
	int ans = 1;
	total += board[ci][cj];
	board[ci][cj] = 0;
	for (int k = 0; k < 4; k++) {
		int ni = ci + di[k];
		int nj = cj + dj[k];
		if (ni < 0 || ni >= boardsize || nj < 0 || nj >= boardsize) continue;
		if (board[ni][nj] > 0) {
			ans += conn(ni, nj);
		}
	}
	return ans;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> Q;
	boardsize = pow(2, N);
	for (int i = 0; i < boardsize; i++) {
		for (int j = 0; j < boardsize; j++) {
			cin >> board[i][j];
		}
	}
	for (int i = 0; i < Q; i++) {
		cin >> L[i];
	}
	for (int q = 0; q < Q; q++) {
		magic(L[q]);
		for (int i = 0; i < boardsize; i++) {
			for (int j = 0; j < boardsize; j++) {
				if (board[i][j] == 0) continue;
				int ice = 0;
				for (int k = 0; k < 4; k++) {
					int ni = i + di[k];
					int nj = j + dj[k];
					if (ni < 0 || ni >= boardsize || nj < 0 || nj >= boardsize) continue;
					if (tmp[ni][nj] > 0) ice++;
				}
				if (ice < 3) {
					board[i][j]--;
				}
			}
		}
	}
	for (int i = 0; i < boardsize; i++) {
		for (int j = 0; j < boardsize; j++) {
			if (board[i][j] > 0) {
				mx = max(mx, conn(i, j));
			}
		}
	}
	cout << total << "\n" << mx;
	return 0;
}