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

문제 링크: www.acmicpc.net/problem/20058

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

1. 주의할 점

- 모든 조건에 맞게 구현한다

- 초기화 작업을 잘 수행한다

- 얼음이 1 줄어드는 경우를 잘 생각한다

 

2. 구현

- 얼음판에 대한 정보를 Arr[][] 배열에 담는다

- 입력받는 변의 크기를 2^num으로 변환한다

- 입력받는 Len의 크기도 변환 후, Rotate() 함수를 통해 회전한다

- 회전이 끝나면 Shrink() 함수를 통해 얼음이 줄어드는 얼음판이 있다면, 1 줄인다. 단, 이때 바로 줄이지 않고 줄어들 얼음판을 표시해놓고 전부 확인이 끝났다면 그때 줄인다

- initialize() 함수를 통해 Check[][] 배열을 초기화한다

- rtnSum() 함수를 통해 얼음판의 총합을 구한다

- find_largest() 함수를 통해 가장 큰 얼음 덩어리의 크기를 반환한다

#include <iostream>
#include <math.h>
#include <queue>
#include <algorithm>
using namespace std;
struct info{
    int x,y;
};
info tmp;
int num,result=0,t;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int arr[64][64],dup[64][64];
bool check[64][64]={false,};

void initialize(){
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++)
            check[i][j]=false;
}

void shrink(){
    initialize();
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++){
            if(arr[i][j]==0) continue;
            int cnt=0;
            for(int k=0;k<4;k++){
                int nx = j + dx[k];
                int ny = i + dy[k];
                if(nx>=0 && ny>=0 && nx<num && ny<num && arr[ny][nx])
                    cnt++;
            }
            if(cnt<3)   check[i][j]=true;
        }
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++)
            if(check[i][j])
                arr[i][j]-=1;
}

int find_largest(){
    initialize();
    int maxi = 0;
    for(int i=0;i<num;i++){
        for(int j=0;j<num;j++){
            if(!check[i][j] && arr[i][j]!=0){
                int cnt=1;
                queue<info> q;
                tmp.x = j;
                tmp.y = i;
                q.push(tmp);
                check[i][j]=true;
                while(!q.empty()){
                    int cx = q.front().x;
                    int cy = q.front().y;
                    q.pop();
                    for(int k=0;k<4;k++){
                        int nx = cx+dx[k];
                        int ny = cy+dy[k];
                        if(nx>=0 && ny>=0 && nx<num && ny<num && !check[ny][nx] && arr[ny][nx]){
                            check[ny][nx]=true;
                            tmp.x=nx;
                            tmp.y=ny;
                            q.push(tmp);
                            cnt++;
                        }
                    }
                }
                maxi = max(maxi,cnt);
            }
        }
    }
    return maxi;
}

void rtnSum(){
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++)
            result+=arr[i][j];
}

void rotate(int y, int x, int len){
    int cnt=0;
    for(int i=y;i<y+len;i++){
        for(int j=x;j<x+len;j++)
            dup[y+j-x][x+len-1-cnt] = arr[i][j];
        cnt++;
    }
    for(int i=y;i<y+len;i++)
        for(int j=x;j<x+len;j++)
            arr[i][j] = dup[i][j];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>> num>>t;
    num = pow(2,num);
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++)
            cin>>arr[i][j];
    for(int m=0;m<t;m++){
        int len;
        cin >> len;
        len = pow(2,len);
        for(int i=0;i<num;i+=len)
            for(int j=0;j<num;j+=len)
                rotate(i,j,len);
        shrink();
    }
    rtnSum();
    cout << result <<"\n"<<find_largest();
    return 0;
}