(C++) - 백준(BOJ) 21609번 : 상어 중학교

www.acmicpc.net/problem/21609

21609번: 상어 중학교

bfs와 정렬을 구현하는 문제였습닌다.

 

풀이방법

 1. 블록 그룹 넓이, 무지개 블록 개수, 기준 블록의 행,열을 struct로 하는 자료구조인 groups vector변수를 선언해줍니다. 그 외 기본적인 입력을 받을 board 등을 선언해줍니다.

 

 2. 조건에 만족하는 블록 그룹의 기준 블록을 찾아줍니다. 무지개 블록은 공유될 수 있기 때문에 check이후 check해제해야합니다. 기준 블록을 찾았으면 groups에 정보들을 넣어줍니다. groups에 정보가 없다면 게임을 끝내고 점수를 출력해줍니다.

 

 3. 정렬 기준에 따라 groups를 정렬 해줍니다. 우선순위가 높은 groups[0]의 정보에 따라 다시 블록 그룹의 영역을 구해 지워줍니다(-2로 만듭니다.) 이 후 지운만큼 points변수에 더해줍니다.

 

 4. 중력을 적용합니다. 열단위로 확인하면서 값들을 갱신해줍니다. -1이상인 블록들의 행을 queue인 block 변수에 넣어주고 -1인 블록의 행은 또 따로 queue인 blackBlock변수에 저장합니다. -1이 아니라면 가장 아래행에서부터 위 행까지 차례대로 넣어줍니다. -1이 나왔다면 blackBlock.front() 자리에 -1을 복귀시켜주고 blackBlock을 pop해줍니다. 그 후엔 -1 위쪽 행부터 시작합니다. 

 

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n, m, board[21][21], ck[21][21], points;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

struct blockInfo {int area,rainbowBlock,standardX,standardY;};
//기준블록, 블록 영역 개수
vector <blockInfo> groups;

bool cmp(blockInfo a, blockInfo b){
    if(a.area == b.area){
        if(a.rainbowBlock == b.rainbowBlock){
            if(a.standardX == b.standardX) return a.standardY > b.standardY;
            return a.standardX > b.standardX;
        }
        return a.rainbowBlock > b.rainbowBlock;
    }
    return a.area > b.area;
}

void releaseRainBowBlock(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(!board[i][j]) ck[i][j] = 0;
        }
    }
}
void findBlockGroup(){
    queue <pii> q;
    memset(ck,0,sizeof(ck));

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            releaseRainBowBlock();
            //없어진곳, 검, 무지개는 안봄
            if(board[i][j] < 0 || !board[i][j] || ck[i][j]) continue;
            //i,j는 기준 블록
            q.push({i,j});
            int area = 1;
            int rainbowBlock = 0;
            ck[i][j] = 1;
            while(!q.empty()){
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                for(int dir = 0; dir < 4; dir++){
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];
                    if(0 > nx || nx >= n || 0 > ny || ny >= n) continue;
                    if(board[nx][ny] != board[i][j] && board[nx][ny] || ck[nx][ny]) continue;
                    if(!board[nx][ny]) rainbowBlock++;
                    ck[nx][ny] = 1;
                    q.push({nx,ny});
                    area++;
                }
            }
            if(area >= 2) groups.push_back({area,rainbowBlock,i,j});
        }
    }
}

void removeMaxBlockGroup(){
    sort(groups.begin(),groups.end(),cmp);
    memset(ck,0,sizeof(ck));
    int originX = groups[0].standardX;
    int originY = groups[0].standardY;
    queue <pii> q;
    queue <pii> removeQ;

    q.push({originX,originY});
    ck[originX][originY] = 1;
    removeQ.push({originX,originY});
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int dir = 0; dir < 4; dir++){
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if(0 > nx || nx >= n || 0 > ny || ny >= n) continue;
            if(board[nx][ny] != board[originX][originY] && board[nx][ny] || ck[nx][ny]) continue;
            ck[nx][ny] = 1;
            q.push({nx,ny});
            removeQ.push({nx,ny});
        }
    }
    while(!removeQ.empty()){
        int x = removeQ.front().first;
        int y = removeQ.front().second;
        removeQ.pop();
        board[x][y] = -2;
    }
    points += groups[0].area * groups[0].area;
}

void rotateBoard(){
    int tmp[21][21];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            tmp[i][j] = board[i][j];

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            board[i][j] = tmp[j][n-i-1];
}

void gravity(){
    for(int i = 0; i < n; i++){
        queue <int> block; //행
        queue <int> blackBlock; //행
        for(int j = n-1; j >= 0; j--){
            if(board[j][i] >= -1) block.push(board[j][i]);
            if(board[j][i] == -1) blackBlock.push(j);
        }

        if(!block.size()) continue;

        for(int j = n-1; j >= 0; j--) board[j][i] = -2;

        for(int j = n-1; j >= 0; j--){
            if(!block.size()) break;
            int val = block.front();
            block.pop();
            if(val == -1){
                int blackRow = blackBlock.front();
                blackBlock.pop();
                board[blackRow][i] = -1;
                j = blackRow;
            }
            else board[j][i] = val;
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> board[i][j];
            
    while(1){
        groups.clear();
        findBlockGroup();
        if(!groups.size()) break;
        removeMaxBlockGroup();
        gravity();
        rotateBoard();
        gravity();
    }
    cout << points << '\n';
}