[백준] 21609번 상어 중학교 (C++)

[문제]

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

21609번: 상어 중학교

 

 

[설명]

- 회전 : 중심 좌표를 구하고, 중심으로 부터 제일 바깥쪽 라인 까지 한 라인씩 큐에 삽입, 대입 하는 과정으로 하 -> 우, 우-> 상 이런식의 반시계 방향을 사용했다. 

- 중력: 한 열씩 맨아래 행부터 확인하며 빈칸이면 해당 행좌표를 BOUND를 기록한뒤 큐에 숫자들을 대입, 끝 혹은 검은색 블록을 만나면 기록된 BOUND부터 채워주는 방식을 사용했다. 

- 구조체 배열 : 각 그룹별로 BFS한뒤 얻게되는 그룹크기, 무지개 수, 최소 행 좌표, 최대 행 좌표를 구조체로 그룹 벡터를 만들어서 사용했다, 우선 순위를 바탕으로 cmp함수를 만들어 정렬후 맨앞에 그룹을 꺼내 제거하는 방식을 사용했다.

 

예외처리랑, 지문을 제대로 안읽어서 한참헤멨다. 3시간 걸린것같다. 

회전은 이전 문제에서 해봤는데도 구현이 조금 시간이 걸렸다. 다른 방법을찾아야 되나... 이전 방법보다 더 나아진 방법을 사용하긴 했는데, 홀수 격자와 짝수 격자를 다른 조건을 줘야할 수 밖에 없어서 둘다 구현 하느라 골치 아팠다.

중력구현도 처음해봤는데, 더 최적화하는 방법이 있는지 봐야겠다. 

[코드]

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second

struct group{
    int x,y; //BFS 시작주소... 잠깐...
    int color;
    int size;
    int rainbow;
    int min_row;
    int min_col;
};
vector <group> groups;
int N, M;
int board[21][21];
bool vis[21][21];
queue <pair<int,int>> q;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

void BFS(int x, int y)
{
    int size = 1;
    int rainbow = 0;
    int min_x = x;
    int min_y = y;


    int color = board[x][y];
    vis[x][y] = 1;
    q.push({x,y});
    while(!q.empty()){
        pair<int, int> cur = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if(nx < 0|| nx >= N|| ny <0 || ny>=N) continue;
            if(vis[nx][ny]) continue;
            if(board[nx][ny] < 0) continue;
            if(board[nx][ny] == color || board[nx][ny] == 0) // 색이 아니거나 무지개면
            {
                if (board[nx][ny] == 0) rainbow++;
                vis[nx][ny] = true;
                size++;
                q.push({nx, ny});
                if(board[nx][ny] == color)
                {
                    min_x = min(nx,min_x);
                    min_y = min(ny,min_y);
                }
            }
        }
    }
    groups.push_back({x,y,color,size,rainbow,min_x,min_y});
}
void rainbow_clear(){
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if(board[i][j] == 0) vis[i][j] = false;
        }
    }
}

bool check(){
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <N; ++j) {
            if(board[i][j] > 0)
                return false;
        }
    }
    return true;
}


bool comp(const group & a,const group & b ){ //최고의 그룹 찾는 비교함수
    if(a.size > b.size) return true;
    else if(a.size == b.size)
    {
        if(a.rainbow > b.rainbow) return true;
        else if(a.rainbow == b.rainbow){
            if(a.min_row > b.min_row) return true;
            else if(a.min_row == b.min_row){
                if(a.min_col > b.min_col) return true;
            }
        }
    }
    return false;
}

void remove(int x,int y){
    int color = board[x][y];
    vis[x][y] = 1;
    board[x][y] = -2; //없애버린 칸은 -2: 벽과 구별, BFS에서도 배제조건은 < 0
    q.push({x,y});
    while(!q.empty()){
        pair<int, int> cur = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if(nx < 0|| nx >= N|| ny <0 || ny>=N) continue;
            if(vis[nx][ny]) continue;
            if(board[nx][ny] < 0) continue;

            if(board[nx][ny] == color || board[nx][ny] == 0) // 색이 아니거나 무지개면
            {
                vis[nx][ny] = true;
                q.push({nx, ny});
                board[nx][ny] = -2;
            }
        }
    }
}


void gravity(){
    queue <int> q;
    for(int i  = 0; i < N; i++){//첫번째 열부터
        int bound = -1;
        bool flag = false;
        for (int j = N-1; j >= 0 ; --j) { //밑바닥부터
            if(board[j][i] == -2 && !flag) {
                bound = j;
                flag = true; //q에담는거... 밑에비어있음.
            }
            if(flag){
                if(board[j][i] == -1){
                    for(int k = bound; k > j; --k){
                        if(!q.empty())
                        {
                            board[k][i] = q.front();
                            q.pop();
                        }
                        else{
                            board[k][i] = -2; //q다주고 남은 공간은 빈공간으로 채움.
                        }
                    }
                    flag = false;
                    bound = j-1;
                }
                else if(board[j][i] == -2) continue;
                else{
                    q.push(board[j][i]);
                }
            }
        }
        if(flag) {
            for (int j = bound; j >= 0; --j) {
                if (!q.empty()) {
                    board[j][i] = q.front();
                    q.pop();
                } else {
                    board[j][i] = -2; //q다주고 남은 공간은 빈공간으로 채움.
                }
            }
        }
    }
}


void turning() { //반시계
    int temp[21][21];
    queue <int> dir[4];//하->우->상->좌
    int center = N / 2;
    if(N % 2 == 0){
        for(int far = 0; far < center; far++){
            for(int st_y = center + far; st_y >= center - far - 1; st_y--)//하
            {
                dir[0].push(board[center + far][st_y]);
            }
            for(int st_x = center - far - 1; st_x <= center + far; st_x++)//우
            {
                dir[1].push(board[st_x][center+far]);
                temp[st_x][center+far] = dir[0].front();
                dir[0].pop();
            }
            for(int st_y = center - 1 - far; st_y <= center + far; st_y++)//상
            {
                dir[2].push(board[center - far-1][st_y]);
                temp[center - far-1][st_y] = dir[1].front();
                dir[1].pop();
            }
            for(int st_x = center + far; st_x >= center - far- 1; st_x--)//좌
            {
                dir[3].push(board[st_x][center-far-1]);
                temp[st_x][center-far-1] = dir[2].front();
                dir[2].pop();
            }
            for(int st_y = center + far; st_y >= center - far - 1; st_y--)//하
            {
                temp[center + far][st_y] = dir[3].front();
                dir[3].pop();
            }
        }
    }
    else{
        temp[center][center] = board[center][center];
        for(int far = 1; far <= center; far++){
            for(int st_y = center + far; st_y >= center - far; st_y--)//하
            {
                dir[0].push(board[center + far][st_y]);
            }
            for(int st_x = center - far; st_x <= center + far; st_x++)//우
            {
                dir[1].push(board[st_x][center+far]);
                temp[st_x][center+far] = dir[0].front();
                dir[0].pop();
            }
            for(int st_y = center - far; st_y <= center + far; st_y++)//상
            {
                dir[2].push(board[center - far][st_y]);
                temp[center - far][st_y] = dir[1].front();
                dir[1].pop();
            }
            for(int st_x = center + far; st_x >= center - far; st_x--)//좌
            {
                dir[3].push(board[st_x][center-far]);
                temp[st_x][center-far] = dir[2].front();
                dir[2].pop();
            }
            for(int st_y = center + far; st_y >= center - far; st_y--)//하
            {
                temp[center + far][st_y] = dir[3].front();
                dir[3].pop();
            }
        }
    }



    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            board[i][j] = temp[i][j];
        }
    }


}
int main(){
    cin >> N >>M;
    if(N == 1) {
        cout << 0;
        return 0;
    }

    for(int i = 0; i < N; i++){
        for (int j = 0; j < N; ++j) {
           cin >> board[i][j];
        }
    }
    int sum = 0;
    while(true){
        for (int i = 0; i < N; ++i) {
            memset(vis[i], false, sizeof(vis[i]));
        }

        groups.clear();
        bool flag = true;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if(!vis[i][j] && board[i][j] > 0) {
                    BFS(i,j); //무지개는 방문안함.
                    rainbow_clear();
                    flag = false;
                }
            }
        }
        if(flag) break;
        sort(groups.begin(), groups.end(),comp); //1단계 끝
        for (int i = 0; i < N; ++i) {
            memset(vis[i], false, sizeof(vis[i]));
        }
        if(groups[0].size == 1) break;
        remove(groups[0].x, groups[0].y);
        sum += groups[0].size * groups[0].size; //2단계 끝.
        gravity(); //3단계 끝.


        turning(); //4단계 끝.
        gravity();

    }
    cout << sum;

}