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

www.acmicpc.net/problem/20058

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

기존의 상어 시리즈와 비슷한 시뮬레이션 문제였습니다.

파이어스톰 시전시 시뮬레이션 과정은 다음과 같습니다.

 

1. 주어진 L값에 따라 얼음판을 시계방향으로 90도 회전한다.
2. 얼음이 있는 칸마다 인접한 칸중에서 얼음이 있는 칸의 개수가 3개 이상이 아니면 해당칸의 얼음의 양이 1줄어든다.

왼쪽부터 각각 회전하기전, L=1, L=2 일때의 얼음판

1번과정을 구현하기 위해 회전하기전 얼음판과 회전후의 얼음판을 비교해보면

얼음판의 회전은 위의 그림에서 초록색 사각형과 같이 (2^L) × (2^L) 크기의 정사각형 단위로 회전이 되므로, 한 단위마다 시계방향으로 90도 회전한 결과를 따로 저장후 기존의 얼음판에 다시 업데이트 해주면 1번과정의 결과를 얻을 수 있습니다.

 

전체코드에서는 얼음판의 한 단위의 시작점을 탐색하는 rotate()함수, 회전한 결과를 업데이트 하는 rotate2()함수로 구현되어 있습니다.

 

2번과정을 구현할때 주의할 점은 얼음의 양이 줄어들 칸을 탐색하면서 바로 1만큼 줄이게 되면, 뒤에서 탐색되는 칸중 얼음의 양이 줄어들면 안되는 칸의 얼음이 1만큼 줄어들 수 있습니다. 따라서 좌표를 따로 저장하여 탐색완료 후 얼음의 양을 줄여주어야 합니다. 해당 과정은 updateIce()함수에 구현되어 있습니다.

 

 

Q번의 파이어스톰 시전과정이 끝난 후 정답을 구하기 위해 아래의 결과를 계산해야 합니다.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

첫번째의 경우 얼음판의 얼음의 양을 모두 더하여 쉽게 구할 수 있으며

두번째의 결과는 BFS또는 DFS를 이용하여 구할 수 있습니다.

두번째 결과를 구할때 주의할 점은 두개 이상의 얼음이 연결된 집합만 덩어리가 되므로 하나의 칸으로만 이루어져 있는 얼음의 집합은 예외처리를 해주어야 합니다.

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
typedef pair<int,int> pii;

int N,Q;
int m[65][65]{};
int mm[65][65]{};
bool vi[65][65]{};
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};

// 집합 탐색
int bfs(int sty, int stx){
    int ret = 1;
    queue<pii> q;
    q.push({sty,stx});
    vi[sty][stx] = true;

    while(!q.empty()){
        int cy = q.front().xx;
        int cx = q.front().yy;
        q.pop();

        for(int i=0; i<4; i++){
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if(ny<0 || nx<0 || ny>=N || nx>=N) continue;
            if(vi[ny][nx] || !m[ny][nx]) continue;
            q.push({ny,nx});
            vi[ny][nx] = true;
            ret++;
        }
    }
    return ret;
}

void updateIce(){
    vector<pii> v;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(m[i][j]==0) continue;
            int adjIce = 0;
            for(int k=0; k<4; k++){
                int ny = i + dy[k];
                int nx = j + dx[k];
                if(ny<0 || nx<0 || ny>=N || nx>=N || m[ny][nx]==0) continue;
                adjIce++;
            }
            if(adjIce < 3) v.push_back({i,j});
        }
    }
    
	// 탐색완료 후 1씩 빼줌
    for(auto n : v)
        m[n.xx][n.yy]--;
}

// 시계방향으로 90도 회전
void rotate2(int y, int x, int n){
    for(int j=x,ii=0; j<x+n; j++,ii++){
        for(int i=y+n-1,jj=0; i>=y; i--,jj++){
            mm[ii][jj] = m[i][j];
        }
    }

    for(int i=y, ii=0; i<y+n; i++, ii++){
        for(int j=x, jj=0; j<x+n; j++, jj++){
            m[i][j] = mm[ii][jj];
        }
    }
}
// 하나의 회전 단위의 시작점 탐색
void rotate(int L){
    int n = 1<<L; // 2^L을 구하기 위한 비트연산
    for(int i=0; i<N; i+=n){
        for(int j=0; j<N; j+=n){
            rotate2(i,j,n);
        }
    }
}

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>>m[i][j];
        }
    }
    int l;
    while(Q--){
        cin>>l;
        if(l) rotate(l);
        updateIce();
    }
    
    // 남아있는 얼음의 합
    int remains=0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            remains += m[i][j];
        }
    }
    cout<<remains<<'\n';
    
    // 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수
    int maxIce = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(vi[i][j] || !m[i][j]) continue;
            maxIce = max(maxIce, bfs(i,j));
        }
    }
    if(maxIce<2) cout<<0; // 한칸 집합 예외처리
    else cout<<maxIce;
}