백준 21609번 - 상어 중학교

• www.acmicpc.net/problem/21609

21609번: 상어 중학교

필요한 배경지식

• BFS

 

 

문제 해결 방법

BFS를 이용한 단순 구현문제였습니다.

문제에서 오토플레이의 과정은 다음과 같습니다.

1. 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
3. 격자에 중력이 작용한다.
4. 격자가 90도 반시계 방향으로 회전한다.
5. 다시 격자에 중력이 작용한다.

 

가장 큰 블록그룹을 찾고 그 점수를 계산하는 함수 findGroup

블록에 중력을 적용시키는 함수 gravity

반시계로 90도 회전시키는 함수 ccRotate

세가지로 나누었습니다. 

 

기준 블록 (1,0)의 그룹 크기

조금 까다로웠던 점은 블록 그룹을 찾는 과정에서 크기가 가장 큰 블록그룹이 여러개이고 무지개 블록의 수도 같을때,

기준 블록의 행과 열의 최대값을 찾아야 해서 방문처리하는 배열을 하나 더 만들어 해결했습니다.

 

findGroup에서 행과 열이 작은순으로 기준 블록을 탐색하여 bfs를 수행하면 무지개 블록도 방문처리가 되어 다음 기준블록에서 그룹탐색시 위의 그림과 같은 정확한 그룹크기를 탐색하지 못합니다. 이때 방문처리 배열을 하나 더 만들어 일반 블록의 방문처리를 따로 저장하면 계속해서 기준 블록을 정하여 그룹의 크기를 탐색할 수 있습니다.

 

이렇게 하면 그룹의 크기, 무지개 블록의 개수가 같은 그룹이 여러개일때 가장 나중에 탐색한 그룹이 제거대상이 됩니다.

 

 

 

전체 코드

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

int N,M, maxn=0, maxzero=0;
int m[21][21]{};
bool vi[21][21]{};
bool colorVi[21][21]{}; // 일반 블럭의 방문처리
bool maxvi[21][21]{};
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};

void ccRotate(){
    int tm[N][N]{};
    for(int j=N-1, ii=0; j>=0; j--, ii++){
        for(int i=0, jj=0; i<N; i++, jj++){
            tm[ii][jj] = m[i][j];
        }
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            m[i][j] = tm[i][j];
        }
    }
}

void gravity(){
    for(int j=0; j<N; j++){
        int bottom = N-1;
        for(int i=N-1; i>=0; i--){
            if(m[i][j]==INF) continue;
            else if(m[i][j]==-1) bottom = i-1;
            else {
                int t = m[i][j];
                m[i][j] = INF;
                m[bottom--][j] = t;
            }
        }
    }
}

pii bfs(int sty, int stx){
    memset(vi,0,sizeof(vi));
    int sum=1, zerosum=0;
    queue<pii> q;
    q.push({sty,stx});
    vi[sty][stx] = true;
    colorVi[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 || vi[ny][nx]) continue;
            if(m[ny][nx]==m[sty][stx] || m[ny][nx]==0) {
                q.push({ny,nx});
                vi[ny][nx] = true;
                if(m[ny][nx]==0) zerosum++;
                else colorVi[ny][nx] = true;
                sum++;
            }
        }
    }
    return pii(sum,zerosum);
}

int ans=0; // score
bool findGroup(){
    bool chk = false;
    maxn = 0, maxzero = 0;
    memset(maxvi,0,sizeof(maxvi));
    memset(colorVi,0,sizeof(colorVi));
    
    // 기준 블록 탐색
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(m[i][j]==INF || m[i][j]==-1 || m[i][j]==0 || colorVi[i][j]) continue;
            pii k = bfs(i,j); // i,j는 기준 블록이 됨
            if(k.xx < 2) continue;
            if(maxn <= k.xx) {
                if(maxn==k.xx && maxzero > k.yy) continue;
                for(int i=0; i<N; i++)
                    for(int j=0; j<N; j++)
                        maxvi[i][j] = vi[i][j];
                maxn = k.xx;
                maxzero = k.yy;
                chk = true;
            }
        }
    }
    if(!chk) return false;
    int cnt = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(maxvi[i][j]) {
                cnt++;
                m[i][j] = INF;
            }
        }
    }
    ans += cnt*cnt;
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin>>m[i][j];
    
    while(findGroup()){
        gravity();
        ccRotate();
        gravity();
    }

    cout<<ans;
}