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

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

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

 

1. 정리

주어진 조건에 대해 전체 맵을 적절히 나누어 회전시키는 로직을 짤 수 있느냐가 관건

 

분할한 맵 좌상단의 좌표가 (i, j), 분할한 맵의 가로,세로 길이를 grid라 할 때 이를 기준으로 활용한다.

분할한 맵에 속한 현재 임의의 좌표를 (p, q) (== (i+y, j+x)), 90도 회전할 좌표를 (a, b)라 할 때

 

1. p가 i로부터 떨어진 거리 == a가 j+(grid-1)로부터 떨어진 거리

2. q가 j로부터 떨어진 거리 == b가 i로부터 떨어진 거리

 

이므로 이를 좌표계에 적용하면

1. a의 좌표 = j + ( grid - 1 ) - ( p - i )

               = j + ( grid - 1 ) - ( i + y - i )

               = j + grid - 1 - y

 

2. b의 좌표 = i + ( q - j )

               = i + ( ( j + x ) - j )

               = i + x

 

나머지 구현에 대한 설명은 생략

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int dy[4] = { -1, 1, 0, 0 }, dx[4] = { 0, 0, 1, -1 };
// int dy[8] = { -1, -1, 0, 1, 1, 1, 0, -1 }, dx[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

int N, Q, n, q, map[65][65], nMap[65][65], L;

void solution(int cn, int grid){
	// 전체 맵 크기 cn X cn
	// 분할한 맵 크기 grid X grid
	// 분할한 맵 좌상단 (i,j)
	// (i+y, j+x)

	for (int i = 1; i <= cn; i+=grid){
		for (int j = 1; j <= cn; j+=grid){
			for (int y = 0; y < grid; y++){
				for (int x = 0; x < grid; x++){
					nMap[(i + x)][j + grid-1 - y] = map[i + y][j + x];
				}
			}
		}
	}

	for (int i = 1; i <= cn; i++)
		for (int j = 1; j <= cn; j++){
			map[i][j] = nMap[i][j];

			int cnt = 0;
			for (int k = 0; k < 4; k++){
				int ny = i + dy[k], nx = j + dx[k];
				if (ny >= 1 && ny <= cn&&nx >= 1 && nx <= cn&&nMap[ny][nx]>0)
					cnt++;
			}
			if (cnt < 3 && map[i][j]>0)
				map[i][j]--;
		}
}

int restOfIce(){
	int res = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			res += map[i][j];

	return res;
}

int bfs(){
	int fRes = 0;

	bool chk[65][65] = { false, };
	queue<pair<int, int>>q;
	
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			if (!chk[i][j] && map[i][j] > 0){
				int res = 0;
				q.push({ i, j });
				chk[i][j] = true;
				res++;

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

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

						if (ny >= 1 && ny <= n&&nx >= 1 && nx <= n&&!chk[ny][nx] && map[ny][nx]>0){
							q.push({ ny, nx });
							chk[ny][nx] = true;
							res++;
						}
					}
				}
				fRes = max(fRes, res);
			}
			chk[i][j] = true;
		}
	}

	return fRes;
}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> Q;
	n = pow(2, N);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < Q; i++){
		cin >> L;
		
		solution(n, pow(2, L));
	}

	cout << restOfIce() << "\n" << bfs();

	return 0;
}