(c++)백준 20058번: 마법사 상어와 파이어스톰

www.acmicpc.net/problem/20058

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

[풀이]

문제에 나와있는 조건을 모두 구현하면 되는 문제였다.

 

구현한 것

1. 2^N * 2^N 얼음판을 2^L * 2^L 크기의 격자로 나누어 시계방향으로 90도 회전

→ 각 격자의 가장 바깥쪽부터 안쪽으로 순서대로 회전시켜주었다. (Turn함수)

 

2. 각 얼음이 있는 칸에 대하여 얼음이 있는 인접한 칸이 3개 미만인 칸 저장(checkSurround함수)

※조건에 해당하는 칸을 볼때마다 -1을 하게 되면 다른 칸을 찾을 때 영향을 주므로 조건에 해당하는 칸의 위치를 모두 찾은 다음 -1 해주기!

 

3. 남아있는 얼음 A[r][c]의 합 구하는 함수(getSum함수)

 

4. 각 덩어리가 차지하는 칸의 개수 구하는 함수(bfs함수)

→ bfs를 사용하여 연결되어 있는 칸의 개수를 센 다음 가장 큰 수를 출력했다.

 

#include <iostream>
#include <cmath>//pow
#include <algorithm>//max
#include <queue>
#include <vector>
using namespace std;

int N, Q;
int A[65][65];
vector<int>L;
bool visited[65][65];//bfs에 사용
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
int totalSize;
vector<pair<int, int>>Minus;//-1해줄 칸

void Turn(int r, int c, int l) {
	int len = pow(2, l);
	//바깥부터 안쪽까지 각 격자 90도 회전
	while (len > 1) {
		vector<int>tmp;
		//윗줄 저장해놓기
		for (int i = c ; i < c + len; i++) {
			tmp.push_back(A[r][i]);
		}
		//왼쪽 세로 -> 위쪽 가로
		int j = c + len - 1;
		for (int i = r; i < r + len; i++) {
			A[r][j] = A[i][c];
			j--;
		}
		//아래쪽 가로 -> 왼쪽 세로
		j = r;
		for (int i = c; i < c + len; i++) {
			A[j][c] = A[r + len - 1][i];
			j++;
		}
		//오른쪽 세로 -> 아래쪽 가로
		j = c;
		for (int i = r + len - 1; i >= r; i--) {
			A[r + len - 1][j] = A[i][c + len - 1];
			j++;
		}
		//위쪽 가로 -> 오른쪽 세로
		for (int i = r + len - 1; i >= r; i--) {
			A[i][c + len - 1] = tmp.back();
			tmp.pop_back();
		}
		len -= 2;
		r++;
		c++;
	}
}

void checkSurround(int r, int c) {
	int cnt = 0;//인접한 얼음이 있는 칸 개수
	for (int i = 0; i < 4; i++) {
		int nr = r + dx[i];
		int nc = c + dy[i];
		if (nr <= 0 || nr > totalSize || nc <= 0 || nc > totalSize)
			continue;
		if (A[nr][nc] > 0)
			cnt++;
	}
	if (cnt < 3)
		Minus.push_back(make_pair(r, c));
}

//남아있는 얼음의 합
int getSum() {
	int res = 0;
	for (int i = 1; i <= totalSize; i++) {
		for (int j = 1; j <= totalSize; j++) {
			res += A[i][j];
		}
	}
	return res;
}

int bfs(int startx, int starty) {
	queue<pair<int, int>>q;
	visited[startx][starty] = true;
	q.push(make_pair(startx, starty));
	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 (nx <= 0 || nx > totalSize || ny <= 0 || ny > totalSize)
				continue;
			//얼음이 있는 칸과 인접해 있으면
			if (A[nx][ny] > 0 && visited[nx][ny] == false) {
				cnt++;
				visited[nx][ny] = true;
				q.push(make_pair(nx, ny));
			}
		}
	}
	return cnt;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> N >> Q;
	totalSize = pow(2, N);//전체 얼음판 크기
	for (int i = 1; i <= totalSize; i++) {
		for (int j = 1; j <= totalSize; j++) {
			cin >> A[i][j];
		}
	}
	int l;
	for (int i = 0; i < Q; i++) {
		cin >> l;
		L.push_back(l);
	}
	//Q번 파이어스톰 시전
	for (int i = 0; i < Q; i++) {
		l = L[i];
		int subSize = pow(2, l);//나눈 격자 하나의 크기
		//모든 부분 격자를 시계방향으로 90도 회전
		for (int r = 1; r <= totalSize - subSize + 1; r += subSize) {
			for (int c = 1; c <= totalSize - subSize + 1; c += subSize) {
				Turn(r, c, l);
			}
		}
		/*
		cout << "Turn" << i+1 << '\n';
		for (int r = 1; r <= totalSize; r++) {
			for (int c = 1; c <= totalSize; c++) {
				cout << A[r][c] << ' ';
			}
			cout << '\n';
		}
		*/
		//얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸 찾기
		for (int r = 1; r <= totalSize; r++) {
			for (int c = 1; c <= totalSize; c++) {
				if (A[r][c] > 0) {
					checkSurround(r, c);
				}
			}
		}
		//얼음 양 - 1
		for (int s = 0; s < Minus.size(); s++) {
			A[Minus[s].first][Minus[s].second]--;
		}
		Minus.clear();
		/*
		cout << "Check" << i + 1 << '\n';
		for (int r = 1; r <= totalSize; r++) {
			for (int c = 1; c <= totalSize; c++) {
				cout << A[r][c] << ' ';
			}
			cout << '\n';
		}
		*/
	}
	//남아있는 얼음 A[r][c]의 합 출력
	cout << getSum() << '\n';
	//가장 큰 덩어리가 차지하는 칸의 개수 구하기
	int Max = 0;
	for (int i = 1; i <= totalSize; i++) {
		for (int j = 1; j <= totalSize; j++) {
			if (A[i][j] > 0 && visited[i][j] == false) {
				Max = max(Max, bfs(i, j));
			}
		}
	}
	cout << Max << '\n';
	return 0;
}