[ BOJ - 20058번 ] 마법사 상어와 파이어스톰 (C++)

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

 

[ 풀이 방법 ] 

1.  2^N x 2^N 크기의 격자를 2^L × 2^L 크기의 부분 격자 2^N-L x 2^N-L 개로 나누는 기능

  - 2중 for 문을 이용해 구현

  - x, y좌표를 0부터 시작해서 2^L씩 더해주며 2^N까지 반복

 

2. 2^L x 2^L 크기의 모든 부분 격자를 시계방향으로 90도 회전하는 기능

  - 2^L × 2^L 크기의 부분 격자의 가장자리를 회전시키는 기능을 구현

  - 부분 격자의 가장자리를 제외한 부분 격자로 줄여나가며 가장자리 회전 기능을 반복하여 구현

 

3. 회전이 끝난 후 격자를 탐색하여 사방에 얼음이 두 방향 이하에만 존재하는 위치에 있는 얼음의 양을 1만큼 줄이는 기능

 

4. 위 기능을 Q번 L을 입력받아 반복하는 기능

 

4. 남은 얼음의 양의 합과 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 구하는 기능

  - visited와 bfs를 이용하여 구현

 

이 때,

1. L이 0인 경우는 회전 기능을 생략해도 된다.

2. 격자를 탐색하여 사방에 얼음이 두 방향 이하에만 존재하는 위치에 있는 얼음의 양을 1만큼 줄이는 기능 구현 시,

  AUX 배열을 사용하여 얼음이 녹는 순서에 상관없이 동시에 얼음이 녹는 것처럼 동작하도록 구현해야 한다.

3. 부분 격자의 크기를 줄이며 회전 기능의 가장자리를 회전 시키는 기능 구현 시, 반복 횟수와 회전 횟수, 줄어든 부분 격자의 크기를 유의하여 구현해야 한다.

 

[ 회고 ]

 부분 격자의 회전이 행과 열 단위가 아닌 원소 단위로 수행된다고 잘못 이해하여 디버깅에 시간이 걸렸으나, 구현 계획과 검증 단계를 확실히 수행한 뒤 구현했기 때문에, 문제를 발견한 뒤 적절히 디버깅하고 구현 계획을 수정하여 문제를 해결할 수 있었다.

 

 구현과 검증에서 실수를 줄이려는 목표는 달성했으나 문제 이해를 확실히하지 못해 푸는데 시간이 걸린 문제였다. 앞으로는 구현 단계 이전에 문제 이해와 접근 방법과 구현 계획, 검증 단계 모두 충분히 시간을 들여야 할 것이다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>

using namespace std;

int P, N, Q, L;
int size;
vector<vector<int>> board;
vector<vector<bool>> visited;

int dirX[4] = {-1, 1, 0, 0};
int dirY[4] = {0, 0, -1, 1};

int res = 0;

void rotate(int I, int J, int k) {
    int x = I+k;
    int y = J+k;
    int p = pow(2, L) - 2*k;
    
    int cnt = p-1;
    while(cnt--) {
    
        int temp = board[x+1][y];
        int prev = board[x][y];
        int next;
        for(int j = y; j < y+p-1; j++) {
            next = board[x][j+1];
            board[x][j+1] = prev;
            prev = next;
        }
        for(int i = x; i < x+p-1; i++) {
            next = board[i+1][y+p-1];
            board[i+1][y+p-1] = prev;
            prev = next;
        }
        for(int j = y+p-1; j > y; j--) {
            next = board[x+p-1][j-1];
            board[x+p-1][j-1] = prev;
            prev = next;
        }
        
        for(int i = x+p-1; i > x; i--) {
            next = board[i-1][y];
            board[i-1][y] = prev;
            prev = next;
        }
        
        board[x][y] = temp;
    }
}

void update() {
    
    vector<vector<int>> aux(board.begin(), board.end());
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(!board[i][j]) continue;
            
            int ice = 0;
            
            for(int dir = 0; dir < 4; dir++) {
                int nx = i + dirX[dir];
                int ny = j + dirY[dir];
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if(!board[nx][ny]) continue;
                
                ice++;
            }
            
            if(ice < 3) aux[i][j]--;
        }
    }
    board.swap(aux);
    vector<vector<int>>().swap(aux);
}

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.emplace(x, y);
    int cnt = 1;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dirX[i];
            int ny = y + dirY[i];
            
            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if(!board[nx][ny]) continue;
            
            if(!visited[nx][ny]) {
                cnt++;
                visited[nx][ny] = true;
                q.emplace(nx, ny);
            }
            
        }
    }
    
    res = max(res, cnt);
}


long long sum() {
    
    long long res = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            res += board[i][j];
        }
    }
    return res;
}

void solve() {
    
    while(Q--) {
        cin >> L;
        
        if (L > 0) {
            int powL = pow(2, L);
            for(int i = 0; i < N; i += powL) {
                for(int j = 0; j < N; j += powL) {
                    for(int k = 0; k < powL/2; k++) {
                        rotate(i, j, k);
                    }
                }
            }
        }
        
        update();
    }
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(!visited[i][j] && board[i][j]) {
                visited[i][j] = true;
                bfs(i, j);
            }
        }
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> P >> Q;
    N = pow(2, P);
    
    board.resize(N, vector<int>(N));
    visited.resize(N, vector<bool>(N));
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    
    solve();
    
    cout << sum() << '\n';
    cout << res << '\n';
    
    return 0;
}