BOJ 20058, 마법사상어와 파이어스톰

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

마법사 상어와 파이어스톰

문제를 요약 해보자면 2^n X 2^n 의 보드판 위에서 크기 L만큼의 격자로 모든 조각을 쪼갠 후에

모든 부분의 격자를 90도 회전 시킨 후 인접한 3개의 칸에 얼음이 없다면 그 칸은 얼음의 양이 1만큼 줄어든다

따라서 bfs로 문제를 해결 할 수 있고, 회전을 구현하는 것이 문제의 핵심이라 할 수 있다

최종적으로는 남아있는 얼음의 양의 합 SUM, 남아있는 얼음 중 가장 큰 덩어리의 칸의 개수를 구하면 되는 문제!

---

PS Logic

1. 격자의 시계방향 회전을 구현할 때 -> 크기 L의 격자에서 가장 왼쪽 위의 좌표를 기준으로 함수를 구현하였다

2. 얼음의 양이 줄어드는 칸을 계산 할때는 줄어드는 칸을 임시 저장 해 둔 후 마지막에 한번에 계산을 해줘야한다 (그렇지 않다면 계산하면서 다른칸에 영향을 미침)

3. BFS로 모든 칸을 돌면서 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 파악

#include <iostream>
#include <cstring>
#define MAX 64
using namespace std;

int N,Q;
int board[MAX][MAX], temp[MAX][MAX];
bool checkMelt[MAX][MAX], visited[MAX][MAX];
const int dy[]={-1,1,0,0};
const int dx[]={0,0,-1,1};

bool inRange(int y,int x){
    return y>=0 && x>=0 && y<N && x<N;
}

int dfs(int y, int x){
    visited[y][x]=true;
    int ret=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        if(inRange(ny,nx) && !visited[ny][nx] && board[ny][nx]>0)
            ret+=dfs(ny,nx);
    }
    return ret;
}

// 가장 큰 덩어리 찾기 - DFS
int getBiggest(){
    int ret=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(board[i][j]>0 && !visited[i][j])
                ret=max(ret,dfs(i,j));
    return ret;
}

// 얼음 합 반환
int getSum(){
    int ret=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            ret+=board[i][j];
    return ret;
}

// 격자 시계방향 회전
void rotate(int y, int x, int L){
    for(int i=0;i<L;i++)
        for(int j=0;j<L;j++)
            temp[i][j]=board[y+L-1-j][x+i];
    for(int i=0;i<L;i++)
        for(int j=0;j<L;j++)
            board[y+i][x+j]=temp[i][j];
}

void solve(int L){
    L=(1<<L);

    // 모든 격자에 대한 회전
    for(int i=0;i<N;i+=L)
        for(int j=0;j<N;j+=L)
            rotate(i,j,L);

    // 얼음 융해
    memset(checkMelt,false,sizeof(checkMelt));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(board[i][j]==0) continue;
            int cnt=0;
            for(int k=0;k<4;k++){
                int ny=i+dy[k];
                int nx=j+dx[k];
                if(!inRange(ny,nx)) continue;
                if(board[ny][nx]>0) cnt++;
            }
            if(cnt<3) checkMelt[i][j]=true;
        }
    }
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(checkMelt[i][j])
                board[i][j]--;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>N>>Q;
    N=(1<<N);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin>>board[i][j];

    while(Q--){
        int L; cin>>L;
        solve(L);
    }

    cout<<getSum()<<'\n';
    cout<<getBiggest()<<'\n';

    return 0;
}