[BOJ] 20058 : 마법사 상어와 파이어스톰

문제 링크

20058번: 마법사 상어와 파이어스톰 (acmicpc.net)

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

마법사 상어 세번째 시리즈. 역시 구현문제다.

풀이

마법사 상어는 이번에 파이어스톰을 배웠다.

상어가 Q번의 명령동안 명령어 L을 입력한다. 그러면 격자를 2^L X 2^L 구간으로 나눠서 각 구간별로 시계방향으로 90도 회전시킨 후, 3개 이상의 얼음과 인접하지 않은 얼음은 양이 1 줄어든다.

N이 입력으로 주어지면 격자의 크기는 2^N X 2^N이 된다.

격자를 각 구간별로 나눠서 시계방향으로 회전한다.

회전 한 후에 모든 격자 칸을 돌면서 인접한 얼음이 3개 이하면 얼음의 양을 1 줄인다. 여기서 모든 칸에서 얼음이 줄어드는 것이 동시에 이루어지므로 양이 줄어들 칸을 따로 표시해 둔 후에 한 번에 양을 줄여주었다.

Q번의 명령 후에, BFS 또는 DFS를 이용해서 가장 큰 덩어리의 크기를 구해주면 된다.

이때 덩어리가 없다면 0을 출력한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 64 + 5;
int N, Q;
int A[MAX_N][MAX_N];
int ans;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int temp[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
int add[MAX_N][MAX_N];
 
void Turn_A(int);
void Melting();
int BFS(pair<int, int>);
bool is_ok(pair<int, int>);
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> Q;
    N = (int)pow(2, N);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> A[i][j];
 
    while (Q--) {
        int L; cin >> L;
        Turn_A(L);
        Melting();
    }
    int total_ice = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            total_ice += A[i][j];
 
    if (total_ice == 0) {
        cout << "0\n" << "0\n";
        return 0;
    }
    cout << total_ice <<"\n";
    int mass = -1;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (!visited[i][j] && A[i][j])
                mass = max(BFS({ i,j }), mass);
        }
    }
    cout << mass << "\n";
    return 0;
}
 
void Turn_A(int size) {
    size = (int)pow(2, size);
    for (int i = 1; i <= N - size + 1; i += size) {
        for (int j = 1; j <= N - size + 1; j += size) {
            memset(temp, 0, sizeof(temp));
            for(int k = 0; k<size; k++)
                for(int p = 0; p<size; p++)
                    temp[k][p] = A[i + k][j + p];
            for (int k = 0; k < size; k++) {
                for (int p = 0; p < size; p++) {
                    A[i + p][j + size - 1 - k] = temp[k][p];
                }
            }
        }
    }
}
 
void Melting() {
    memset(add, 0, sizeof(add));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (!A[i][j])
                continue;
            int cnt = 0;
            for (int k = 0; k < 4; k++)
                if (A[i + dy[k]][j + dx[k]])
                    cnt++;
            if (cnt < 3)
                add[i][j] = -1;
        }
    }
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            A[i][j] += add[i][j];
}
 
bool is_ok(pair<int, int> next) {
    if (next.first < 1 || next.first > N || next.second < 1 || next.second > N
        || visited[next.first][next.second] || !A[next.first][next.second])
        return false;
    return true;
}
 
int BFS(pair<int, int> st) {
    queue<pair<int, int>> q;
    q.push(st);
    int cnt = 0;
    while (!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();
        if (visited[now.first][now.second])
            continue;
        visited[now.first][now.second] = true;
        cnt++;
        for (int i = 0; i < 4; i++) {
            pair<int, int> next = { now.first + dy[i], now.second + dx[i] };
            if (is_ok(next))
                q.push(next);
        }
    }
    return cnt;
}

문제를 잘못이해해서 가장 큰 얼음이 들어있는 덩어리의 크기를 출력하는 것인 줄 알았다.

그렇게 한참을 헤맨후에 문제를 다시 읽고 알았다.