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

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

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

 

 

알고리즘 종류

구현

 

 

사고 과정

1. 회전시키기

- 격자 모양으로 이동하기 위해서 2^L 만큼 이동한다.

- 격자 모양의 좌측 상단 위치에서 차례대로 회전한다.

- 아래 이미지처럼 주황색(원본 배열)에서 빨강색(임시 배열)으로 옮기고 다시 주황색으로 옮길 것이다. 시계방향 90도 회전은 (i, j) => (j, 길이-1 - i) 이다. 이때, 격자 모양의 초기 위치(격자마다 좌측 상단의 위치)가 다르므로, 원본의 (y+i, x+j)을 임시 배열의 (j, 길이-1 - i)로 회전시켜서 옮겨준다. 그러면 원본의 값은 항상 좌측 상단이 (0,0)인 곳으로 옮겨진다. 아래 이미지에서, 주황색의 배열이 회전하면 빨강색으로 이동한다. [y와 x는 주황색에서 위치이다. 예: (0,4)]

이렇게 옮겨진 값들을 다시 주황색(원본 배열)로 옮길 것이다. 빨강색의 (i, j)에 주황색의 (y, x)를 더해주면 된다.

 

 

2. 녹이기

- 동시에 녹아야 한다. 동시에 녹이기 위해서는 녹을 위치를 선택하고, 모두 선택했으면 녹여준다.

 

3. 얼음 총량 구하기

4. 최대 크기 얼음 덩어리 구하기

 

 

구현(C++)

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
 
int n, q;
int len;
 
int mat[70][70]; // 원본  
int mat2[70][70]; // 임시 저장  
int isVisited[70][70];
vector<int> v;
 
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
 
bool isValid(int y, int x){
    return (y>=0&&y<len) && (x>=0&&x<len);
}
 
 
void rotation(int y, int x, int size){
    
    for(int i=0; i<size; i++){
        for(int j=0; j<size; j++){
            mat2[j][size-i-1] = mat[y+i][x+j]; // 회전시켜서 저장  
        }
    }
    
    for(int i=0; i<size; i++){
        for(int j=0; j<size; j++){
            mat[y+i][x+j] = mat2[i][j]; // 저장된 값을 다시 옮기기  
        }
    }
}
 
 
void melt(){
    memset(mat2, 0, sizeof(mat2)); // 녹을 얼음 표시할 배열  
    
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            
            int cnt=0;
            for(int d=0; d<4; d++){
                int ny = i+dir[d][0];
                int nx = j+dir[d][1];
                
                if(!isValid(ny, nx)) continue;
                if(mat[ny][nx]<=0) continue;
                
                cnt++;
            }
            if(cnt < 3) mat2[i][j] = -1; // 녹을 얼음 표시                                  
        }
    }
    
    // 표시된 얼음 녹이기  
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            if(mat2[i][j] == -1) mat[i][j]--;
        }
    }
}
 
int bfs(int y, int x){
    
    queue<pair<int, int> > q;
    q.push({y, x});
    isVisited[y][x] = 1;
    int cnt=1;
    
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        for(int d=0; d<4; d++){
            int ny = y + dir[d][0];
            int nx = x + dir[d][1];
            
            if(!isValid(ny, nx)) continue;
            if(isVisited[ny][nx]) continue;
            if(mat[ny][nx] <= 0) continue;
            
            isVisited[ny][nx] = 1;
            cnt++;
            q.push({ny, nx});
        }
    }
    return cnt;
}
 
 
void solution(){
    
    for(int k=0; k<q; k++){
        int size = pow(2, v[k]);
        
        for(int i=0; i<len; i+=size){
            for(int j=0; j<len; j+=size){
                rotation(i, j, size);
            }
        }
        melt();
    }
    
    // 얼음 총량  
    int total=0;
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            if(mat[i][j] > 0) total += mat[i][j];
        }
    }
    
    // 가장 큰 얼음 덩어리  
    int max_ice=0;
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            if(!isVisited[i][j] && mat[i][j] > 0){
                max_ice = max(max_ice, bfs(i,j));
            }
        }
    }
    
    cout << total << endl;
    cout << max_ice << endl;
    
}
 
int main(void){
    
    cin >> n >> q;
    len = pow(2,n);
    
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            cin >> mat[i][j];
        }
    }
    
    for(int i=0; i<q; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    
    solution();
}

 

 

시행착오