문제

21609번: 상어 중학교

풀이

bfs를 사용하는 구현문제 입니다. 알고리즘은 복잡하지 않아 구현만 잘하면 풀 수 있었네요.

문제의 오토플레이가 요구하는 4가지 기능을 구현해야 합니다.

1. 가장 큰 블록그룹 찾기
2. 찾은 블록그룹 삭제하기
3. 중력 작용하기
4. 격자 반시계로 90도 회전하기

1. 가장 큰 블록그룹 찾기
bfs탐색을 통해 같은 색상 블록의 그룹을 찾으면 되겠습니다.

무지개 블록은 주의해야 하는데, 크기가 같은 블록 그룹이 생길 수 있기 때문에 무지개 블록을 탐색하게 되면 따로 vector에 모아두었다가 그 개수를 활용해야 합니다.
또 무지개 블록은 한 색상에 대해 탐색할때 탐색이 되어도, 다른 색상블록에 의해 다시 탐색될 수 있어야 하기 때문에 한가지 색상블록에 대한 bfs 탐색이 끝난 뒤 vector에 모아둔 무지개 블록들의 visited를 false로 변경해야 합니다.

bfs 시작점을 전체 격자의 왼쪽 위 부터 오른쪽 아래 순서로 결정 하기 때문에 시작점이 기준블록이 됩니다. 또한 자연스럽게 크기가 같고 무지개 블록의 개수도 같은 블록 그룹이 생긴다면 나중에 탐색된 그룹을 선택하면 되겠네요.

2. 찾은 블록그룹 삭제하기
1번에서 찾은 그룹을 차례대로 삭제하면 됩니다. 이때 저는 삭제된 블록의 위치를 -2로 표현 하였는데, 몇가지 장점이 있습니다.

bfs 시작점을 찾을 때 블록표현값 < 1 인 경우에만 시작점으로 선택하게 할 수 있습니다.
중력 작용 함수에서 중력이 작용할 블록은 블록표현값 < 0으로 조건을 걸 수 있습니다.

3. 중력 작용하기
중력이 정상적으로 작용하기 위해 가장 아래의 블록들부터 움직여야 합니다.
움직일 블록의 바로 밑블록부터 수직 아래 방향의 블록들을 탐색하는데, 빈블럭이 아닌경우(-2)를 만나게 될때까지 반복하며 한칸씩 아래로 탐색합니다. 빈 블록이 아닌 블록을 만나게 되면 그 위치의 한칸 위가 움직일 블록의 새로운 위치입니다.

4. 회전하기
임시로 새로운 위치의 값들을 저장할 temp 격자를 만들어 temp[i][j] = board[j][-i+n-1]로 각블록들을 이동 시킨 뒤 board = temp로 변경하여 구현합니다.

필요한 기능을 모두 구현했다면 순서대로 배치하고 반복시킵니다.
종료 시점은 찾은 블록그룹의 개수가 2개 미만이라면 break를 통해 반복을 탈출합니다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector<vector<int>> board;

vector<pair<int, int>> dir { {0,1}, {0,-1}, {1,0}, {-1,0} };

bool OOB(int x, int y) { return x < 0 || x >= n || y < 0 || y >= n; }
int max(int a, int b) { return a > b ? a : b; }

vector<pair<int, int>> bfs(int x, int y, vector<vector<bool>>& visited, int& rainbowCnt)
{
    vector<pair<int, int>> ret;
    int color = board[x][y];
    vector<pair<int, int>> rainbow;
    queue<pair<int, int>> q;

    q.push({x, y});
    ret.push_back({x, y});
    visited[x][y] = true;

    while (!q.empty())
    {
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();

        for (auto d: dir)
        {
            int nX = d.first + curX;
            int nY = d.second + curY;

            if (OOB(nX, nY) || visited[nX][nY])
                continue;

            if (board[nX][nY] != 0 && board[nX][nY] != color)
                continue;

            if (board[nX][nY] == 0) // 무지개 블록은 bfs 탐색 후에 다른 색상의 블록이 사용할 수 있도록 visited = false로 변경해주어야한다.
                rainbow.push_back({nX, nY});
            visited[nX][nY] = true;
            ret.push_back({nX, nY});
            q.push({nX, nY});
        }
    }
    for (auto rb : rainbow)
        visited[rb.first][rb.second] = false;

    rainbowCnt = rainbow.size();
    return ret;
}

vector<pair<int, int>> findBlock(pair<int, int>& pos) // return blockSize, pos = 블럭의 기준 위치
{
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    vector<pair<int, int>> selected;
    int selectedRainbow = 0;
    
    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<n; ++j)
        {
            if (board[i][j] < 1) // 무지개, 검정 블록, -2는 비어있는 칸으로 처리
                continue;

            if (visited[i][j])
                continue;
            
            int bufferRainbow = 0;
            vector<pair<int, int>> buffer = bfs(i, j, visited, bufferRainbow);

            if (buffer.size() < selected.size())
                continue;
            if (buffer.size() == selected.size())
            {
                if (bufferRainbow < selectedRainbow)
                    continue;
            }

            selected = buffer;
            pos = {i, j};
            selectedRainbow = bufferRainbow;
        }
    }

    return selected;
}

int deletBlock(vector<pair<int, int>> blocks)
{
    int ret = 0;
    for (auto block : blocks)
    {
        int x = block.first;
        int y = block.second;

        board[x][y] = -2;
        ++ret;
    }

    return ret * ret;
}

void gravity()
{
    for (int i=n-1; i >=0; --i)
    {
        for (int j=n-1; j>=0; --j)
        {
            if (board[i][j] < 0) // -1, -2 인 경우 넘어간다.
                continue;;

            int height = n-1;
            for (int h=i+1; h<n; ++h)
            {
                if (board[h][j] != -2)
                {
                    height = h-1;
                    break;
                }
            }
            
            if (height != i)
            {
                board[height][j] = board[i][j];
                board[i][j] = -2;
            }
        }
    }
}

void rotate()
{
    vector<vector<int>> temp(n, vector<int>(n));
    for (int i=0; i<n; ++i)
    {
        for(int j=0; j<n; ++j)
        {
            temp[i][j] = board[j][-i+n-1];
        }
    }

    board = temp;
}

int main ()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    board.resize(n, vector<int>(n));
    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<n; ++j)
        {
            cin >> board[i][j];
        }
    }
    
    int score = 0;
    while (true)
    {
        // find large block
            // block size < 2 : break;
        pair<int, int> pos;
        vector<pair<int, int>> blocks = findBlock(pos);
        if (blocks.size() < 2)
            break;
        
        // delet block, add score
        score += deletBlock(blocks);

        // gravity
        gravity();

        // rotate
        rotate();

        // gravity
        gravity();
    
    }

    cout << score << endl;
    return 0;
}

/*
기준 블록: 무지개가 아닌 행이 가장 작고, 열이 가장 작은 블록
찾을 블록: 크기가 가장 큰 블록 중, 무지개 블록이 많은 블록, 행이 가장 크고 열이 가장 큰 블록
격자는 반시계 회전
*/