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

문제

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

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

---

접근방법

1) 접근 사고

1. 입력받은 배열들을 2^L * 2^L 로 나눈다.

2.이후 모든 분리된 격자를 시계 방향으로 90도 회전한다.

3.Board에 모든 얼음들을 돌면서 인접해 있는 얼음이 3개가 아닌 경우는 1씩 감축한다.

4.이중 반복문을 활용한 얼음의 총합값과, BFS를 활용한 가장 큰 얼음 덩어리를 탐색하여 정답을 반환한다.

 

2) 시간 복잡도

O(n ^ 3)

 

3) 실수

1. Board에 모든 얼음들을 1씩 감축해주는 과정에서 감축할 얼음들을 전부 확인하고 한 번에 감축시켜야 했는데(하지 않을 도미노처럼 잘못된 얼음이 연속적으로 녹아버리는 경우가 존재함) 조건에 맞는 경우 바로 감축시켜 오답 처리를 받음.

2.회전을 할 경우 memcpy의 무분별한 사용으로 시간 초과가 발생. board[x + (i - j)][i + (1 << value) - (x + 1) + j] 기억하자..

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
 
using namespace std;
const int MAX = 1 << 7;
 
int my[] = {-1,0,1,0};
int mx[] = {0,-1,0,1};
 
struct game{
    int n, q;
    int board[MAX][MAX];
    vector<int> L;
    game(int n, int q) : n(n), q(q), L(q) {}
 
    //범우 초과 확인
    bool isvalid(int y, int x){
        return (y >= 0 && y < n && x >= 0 && x < n);
    }
    
    //입력값
    void init(){
        n = (1 << n);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cin >> board[i][j];
            }
        }
       for(int i = 0; i < q; i++){
           cin >> L[i];
       }
    }
 
    //회전해주기 위한 배열의 시작점을 탐색
    void divide(){
        for(int t = 0; t < q; t++){
            int powValue = L[t];
            for(int i = 0; i < n; i+= (1 << powValue)){
                for(int j = 0; j < n; j+=(1 << powValue)){
                    rotate(i, j, powValue);
                }
            }
            minusIce();
        }
    };
 
    //board를 회전하는 함수
    void rotate(int i, int j, int l){
        int tmpA[MAX][MAX];
        for (int y = i; y < i + (1 << l); y++)
            for (int x = j; x < j + (1 << l); x++)
                tmpA[y][x] = board[y][x];
 
            for (int y = i; y < i + (1 << l); y++)
                for (int x = j; x < j + (1 << l); x++)
                    board[x + i - j][i + (1 << l) - (y + 1) + j] = tmpA[y][x];
    }
 
    //얼음의 조건이 안될 경우 1을 감축
    void minusIce(){
        queue<pair<int,int>> q;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                //0인 경우는 얼음이 아니므로 넘겨야 한다. 이 조건을 안 넣어주어서 시간을 많이 소모
                if(board[i][j] == 0)
                    continue;
                int cnt = 0;
                for(int d = 0; d <4; d++){
                    int ny = i + my[d];
                    int nx = j + mx[d];
                    if(!isvalid(ny, nx))
                        continue;
                    if(board[ny][nx] == 0)
                        continue;
                    cnt++;
                }
                if(cnt < 3)
                    q.push({i, j});
            }
        }
 
        while(!q.empty()){
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            board[y][x]--;
        }
    }
 
    //얼음의 총합 반환 
    int sumIce(){
        int sum = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                sum += board[i][j];
            }
        }
        return sum;
    }
 
    //가장 큰 얼음을 반환하는 함수
    int landCnt(){
        bool visited[1 << 7][1 << 7];
        memset(visited, false, sizeof visited);
        int ret = 0;
 
        for(int i = 0; i < n ; i++){
            for(int j = 0; j < n; j++){
                auto BFS = [&](int y, int x) -> int{
                   queue<pair<int,int>> q;
                   q.push({y, x});
                   visited[y][x] = true;
                   int cnt = 0;
                   while(!q.empty()){
                       auto[cy, cx] = q.front();
                       q.pop();
 
                       if(board[cy][cx] > 0)
                        cnt++;
 
                       for(int d = 0; d < 4; d++){
                           int ny = cy + my[d];
                           int nx = cx + mx[d];
 
                           if(isvalid(ny, nx)){
                               if(board[ny][nx] != 0 && !visited[ny][nx]){
                                  // cout << "ny : " << ny << " nx" << nx <<"\n";
                                   q.push({ny, nx});
                                   visited[ny][nx] = true;
                               }
                           }
                       }
                   }
                   return cnt;
               };
                if(!visited[i][j] && board[i][j])
                    ret = max(ret, BFS(i, j));
            }
        }
        return ret;
    }
 
    void printBoard(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cout << board[i][j] << " ";
            }
            cout <<"\n";
        }
        cout <<"=========board========" <<"\n";
    }
};
 
int main(){
    int n, q;
    cin >> n >> q;
    game op(n, q);
    op.init();
    op.divide();
    cout << op.sumIce() <<"\n";
    cout << op.landCnt() <<"\n";
}