상어 중학교

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

21609번: 상어 중학교

블록 그룹을 만들 때 구조체를 써야할 거 같다.

1. 그룹의 크기
2. 무지개 블럭 개수
3. 무지개 블럭이 아닌
기준 블록의 행, 열
4. 블럭 그룹에 속한 블럭들의 좌표
vector<pair<int, int>>

이 문제의 핵심은
그룹을 나누는 것이다.

 

그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다.

검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다.

 

단순하게 visited를 이용해서 BFS를 하면 안된다!

무지개 블록은 "중복이 가능"하기 때문이다.

그럼 어떻게? 무지개 전용 visited를 만들어 따로 처리하자.

 

연산자 오버로딩 -> sort는 반대!

 

gravity() 함수

https://larc-en-ciel.tistory.com/225

모노미노도미노 2

여기서 다뤘다.

void gravity()
{
    for (int i = n - 2; i >= 0; i--)
    {
        for (int j = 0; j < n; j++)
        {
            // 제거 되었거나 검정 블럭은 못움직이니까
            if (map[i][j] == -2)
                continue;
            if (map[i][j] == -1)
                continue;
 
            int color = map[i][j];
            int nx = i + 1;
            while (true)
            {
                if (map[nx][j] != -2)
                    break;
                if (nx == n)
                    break;
                nx++;
            }
            // 마지막에 하나 빼줘야한다
            nx--;
 
            // 원래 위치는 빈공간으로 만들고
            map[i][j] = -2;
            // 중력 적용
            map[nx][j] = color;
        }
    }
}

 

배열 돌리기

배열 반시계 방향 돌리기

이중 for문에 변수 4개를 써서 만든다!!

void rotate()
{
    int tmp[25][25] = { 0, };
 
    for (int i = 0, y = n - 1; i < n; i++, y--)
    {
        for (int j = n - 1, x = n - 1; j >= 0; j--, x--)
        {
            tmp[i][j] = map[x][y];
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            map[i][j] = tmp[i][j];
    }
 
}
 

<소스코드>

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
int n, m;
int ans = 0;
int map[25][25];
// 일반 블럭용 방문 배열
bool visited[25][25];
 
// 무지개 블럭은 중복이 가능하다
// 무지개 블럭용 방문 배열
bool r_visited[25][25];
 
struct block
{
    int kugi;
    int rainbow_cnt;
    int row;
    int col;
    // 영역 안에 포함된 블럭들 위치 저장 벡터
    vector<pair<int, int>> v;
};
 
// sort 연산자 오버로딩!
bool operator < (const pair<int, int>& a, const pair<int, int>& b)
{
    if (a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}
 
// 구조체 비교 연산자 오버로딩
bool operator < (const block& a, const block& b)
{
    if (a.kugi == b.kugi)
    {
        if (a.rainbow_cnt == b.rainbow_cnt)
        {
            if (a.row == b.row)
            {
                return a.col < b.col;
            }
            return a.row < b.row;
        }
        return a.rainbow_cnt < b.rainbow_cnt;
    }
    return a.kugi < b.kugi;
}
 
block bfs(int a, int b, int color)
{
    memset(r_visited, false, sizeof(r_visited));
 
    // 전체 영역 좌표 저장
    vector<pair<int, int>> kuiki;
    // 기준 블럭은 무지개 안됨
    // 무지개 뺀 블럭들의 좌표
    vector<pair<int, int>> no_rainbow;
    // bfs 큐
    queue<pair<int, int>> q;
    
    kuiki.push_back(make_pair(a, b));
    no_rainbow.push_back(make_pair(a, b));
    q.push(make_pair(a, b));
    visited[a][b] = true;
    int rainbow = 0;
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++)
        {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n)
            {
                // 무지개 블럭
                if (map[nx][ny] == 0)
                {
                    if (r_visited[nx][ny] == false)
                    {
                        r_visited[nx][ny] = true;
                        rainbow++;
                        kuiki.push_back(make_pair(nx, ny));
                        q.push(make_pair(nx, ny));
                    }
                }
                else if (map[nx][ny] == color)
                {
                    if (visited[nx][ny] == false)
                    {
                        visited[nx][ny] = true;
                        q.push(make_pair(nx, ny));
                        kuiki.push_back(make_pair(nx, ny));
                        no_rainbow.push_back(make_pair(nx, ny));
                    }
                }
            }
        }
    }
 
    sort(no_rainbow.begin(), no_rainbow.end());
    block r_block;
    r_block.kugi = kuiki.size();
    r_block.rainbow_cnt = rainbow;
    r_block.row = no_rainbow[0].first;
    r_block.col = no_rainbow[0].second;
    r_block.v = kuiki;
    return r_block;
}
 
// 가장 큰 영역 찾기
block finding_big()
{
    memset(visited, false, sizeof(visited));
    block result;
    result.kugi = -1;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (visited[i][j] == true)
                continue;
            if (map[i][j] == -2 || map[i][j] == -1 || map[i][j] == 0)
                continue;
 
            block tmp_result = bfs(i, j, map[i][j]);
 
            // -1이면 초기값 tmp_result로 초기화
            if (result.kugi == -1)
                result = tmp_result;
            else
            {
                if (result < tmp_result)
                    result = tmp_result;
            }
        }
    }
    return result;
}
 
void delete_block(block result)
{
    vector<pair<int, int>> arr = result.v;
    for (int i = 0; i < arr.size(); i++)
    {
        int x = arr[i].first;
        int y = arr[i].second;
        map[x][y] = -2;
    }
    ans += (arr.size() * arr.size());
}
 
void gravity()
{
    for (int i = n - 2; i >= 0; i--)
    {
        for (int j = 0; j < n; j++)
        {
            // 제거 되었거나 검정 블럭은 못움직이니까
            if (map[i][j] == -2)
                continue;
            if (map[i][j] == -1)
                continue;
 
            int color = map[i][j];
            int nx = i + 1;
            while (true)
            {
                if (map[nx][j] != -2)
                    break;
                if (nx == n)
                    break;
                nx++;
            }
            // 마지막에 하나 빼줘야한다
            nx--;
 
            // 원래 위치는 빈공간으로 만들고
            map[i][j] = -2;
            // 중력 적용
            map[nx][j] = color;
        }
    }
}
 
void rotate()
{
    int tmp[25][25] = { 0, };
 
    for (int i = 0, y = n - 1; i < n; i++, y--)
    {
        for (int j = n - 1, x = n - 1; j >= 0; j--, x--)
        {
            tmp[i][j] = map[x][y];
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            map[i][j] = tmp[i][j];
    }
 
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cin >> map[i][j];
    }
 
    while (true)
    {
        block result = finding_big();
        // 영역이 더 이상 없음
        if (result.kugi < 2)
            break;
        delete_block(result);
        gravity();
        rotate();
        gravity();
    }
    cout << ans << '\n';
 
    return 0;
}