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

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

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

문제

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.

파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법을 시전하기 전	L = 1	L = 2

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

입력

첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.

출력

첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.

 

뭔가 구현은 하라는대로 하면 되는데 은근 구현하기 까다로웠던 문제라 2시간이 넘게 걸린 문제이다.

일단 까다로웠던 부분은 시계 방향으로 회전시키는 부분. (이건 내가 부족해서 시간이 오래 걸렸다)

그리고 얼음이 줄어드는 조건을 해석하는데 오래 걸렸다. 문제 지문이 나한테는 너무 헷갈렸다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321
using namespace std;

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

int N, Q, range, Power, Total, Answer, Cnt_Ice;
int adj[70][70];
int copy_adj[70][70];
bool visited[70][70];

const int dy[] = { 1,-1 ,0,0 };
const int dx[] = { 0,0,1,-1 };
queue<pair<int, int>> q;

int isValid(int y, int x) {
	return (1 <= y && y <= range && 1 <= x && x <= range);
}

void Copy() {
	for (int i = 1; i <= range; i++) {
		for (int j = 1; j <= range; j++) {
			copy_adj[i][j] = adj[i][j];
		}
	}
}

void Check_Ice(int y, int x) {
	int Cnt = 0;
	for (int i = 0; i < 4; i++) {
		int nextY = dy[i] + y;
		int nextX = dx[i] + x;

		if (!isValid(nextY, nextX)) {
			Cnt++;
			continue;
		}
		if (adj[nextY][nextX] > 0) continue;
		else Cnt++;
	}

	if (Cnt >= 2 && adj[y][x] > 0) q.push({ y,x });
}

void FireStorm() {
	while (!q.empty()) {
		int a = q.front().first;
		int b = q.front().second;
		q.pop();

		adj[a][b]--;
	}
}

void Rotate(int y, int x,int l) {
	int newY = y + l - 1;
	int newX = x;
	for (int i = y; i < y + l; i++) {
		int TempY = newY;
		int TempX = newX;
		for (int j = x; j < x + l; j++) {
			adj[i][j] = copy_adj[TempY][TempX];
			TempY--;
		}
		newX++;
	}
}

void DFS(int y, int x) {
	Cnt_Ice++;
	visited[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int nextY = y + dy[i];
		int nextX = x + dx[i];

		if (!isValid(nextY, nextY)) continue;
		if (!visited[nextY][nextX] && adj[nextY][nextX] != 0) DFS(nextY, nextX);
	}
}

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

	cin >> N >> Q;
	range = (int)pow(2, N);

	for (int i = 1; i <= range; i++) {
		for (int j = 1; j <= range; j++) {
			cin >> adj[i][j];
		}
	}

	while (Q--) {
		cin >> Power;
		Power = (int)pow(2, Power);

		Copy();
		for (int i = 0; i < range / Power; i++) {
			for (int j = 0; j < range / Power; j++) {
				Rotate(i * Power + 1, j * Power + 1, Power);
			}
		}

		for (int i = 1; i <= range; i++) {
			for (int j = 1; j <= range; j++) {
				if (adj[i][j] == 0) continue;
				Check_Ice(i, j);
			}
		}
		FireStorm();
	}

	for (int i = 1; i <= range; i++) {
		for (int j = 1; j <= range; j++) {
			if (!adj[i][j]) continue;
			Total += adj[i][j];
		}
	}

	for (int i = 1; i <= range; i++) {
		for (int j = 1; j <= range; j++) {
			if (!visited[i][j] && adj[i][j] != 0) {
				Cnt_Ice = 0;
				DFS(i, j);
				Answer = max(Answer, Cnt_Ice);
			}
		}
	}

	cout << Total << endl;
	cout << Answer << endl;
	return 0;
}