[BOJ] 21609 : 상어 중학교

문제 링크

21609번: 상어 중학교 (acmicpc.net)

21609번: 상어 중학교

상어 초등학교에 이어서 상어 중학교 문제. 역시 구현문제다.

풀이

N x N으로 주어진 격자를 주어진 과정에 따라 블록그룹을 삭제하는 게임.

최종 점수를 출력하자.

블록 그룹에는 반드시 같은 색깔의 블록들이 포함되어야하며, 무지개 블록은 어느 그룹에나 포함될 수 있다. 그리고 검은색 블록은 어떤 그룹에도 들어갈 수 없다. 이때 블록그룹에 일반 블록이 1개 이상 들어가야하며 그룹의 크기는 2 이상이어야 한다.

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

점수획득 과정은 위와 같다.

먼저 저장하고 있어야 할 정보들이 뭐가 있는지 생각해보자.

1. 현재 격자판의 상황을 저장해야한다.

A[20][20] 의 배열을 만들어서 저장해두었다.

2. 블록 그룹을 탐색할 때 해당 칸의 블록이 이미 어떤 블록그룹에 포함되어 있는지를 표시하기 위해

visited[20][20] 배열을 만들어서 소속 블록그룹이 있는지를 체크했다.

이때 무지개 블록은 모든 그룹에 포함될 수 있으므로 탐색 전 무지개 블록의 visited는 항상 false 여야한다.

인접한 블록끼리 서로 이동할 수 있어야 한다는 조건이 있으므로 BFS를 이용해서 탐색했다. 그리고 인접한 블록이 같은 색이거나 무지개 블록이면 같은 그룹의 블록이라 판단했다.

3. 블록 그룹에 대한 정보를 저장할 벡터

탐색 후 여러 블록 그룹에 대한 정보를 저장해야 어떤 블록 그룹이 가장 큰지, 무지개 블록이 몇개나 포함되었는지를 판단 할 수 있다.

과정 1번에 보면

1. 크기가 가장 큰 블록 그룹을 찾는다.
그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹,
그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 
그 것도 여러개이면 열이 가장 큰 것을 찾는다.​

라고 되어있다.

그렇다면 블록 그룹에 대한 정보를 저장할 때 블록 그룹의 크기, 포함된 무지개 블록의 수, 기준 블록의 좌표

를 저장하고 있어야 지워야할 블록 그룹을 선정할 수 있다.

vector<pair<pair<int,int>,pair<int,int>>> 로 벡터를 만들어서 이 세가지 정보를 저장했다.

그리고 vector를 내림차순으로 정렬한다면 위의 조건을 만족하는 블록그룹이  0번 인덱스에 올 것이다.

0번 인덱스에 있는 블록그룹의 기준 블록의 좌표를 이용해서 해당 그룹의 블록들을 모두 지운다.

나는 블록 색이 -2이면 없는 블록이라고 생각했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 20 + 5;
int N, M;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int A[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
int Score;
vector<pair<pair<int, int>, pair<int, int>>> Block_Group;
void Find_Group(pair<int,int>);
bool is_ok(pair<int, int> now);
void Erase_Group();
void Gravity();
void Rotate();
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> A[i][j];
        }
    }
    while (true) {
        memset(visited, false, sizeof(visited));
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (!visited[i][j] && A[i][j] > 0) {
                    Find_Group({ i,j });
                }
            }
        }
        if (Block_Group.empty())
            break;
        sort(Block_Group.begin(), Block_Group.end(), greater<pair<pair<int, int>, pair<int, int>>>());
        if (Block_Group[0].first.first < 2)
            break;
        Erase_Group();
        Gravity();
        Rotate();
        Gravity();
    }
    cout << Score << "\n";
    return 0;
}
 
void Find_Group(pair<int, int> st) {
    queue<pair<int, int>> q;
    q.push(st);
    int Color = A[st.first][st.second];
    pair<int, int> Criterion = st;
    int cnt_B = 0;
    vector<pair<int, int>> Rainbow;
    while (!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();
        if (visited[now.first][now.second])
            continue;
        visited[now.first][now.second] = true;
        cnt_B++;
        if (A[now.first][now.second] != 0) {
            if (Criterion.first > now.first)
                Criterion = now;
            else if (Criterion.first == now.first)
                Criterion.second = min(Criterion.second, now.second);
        }
        else Rainbow.push_back(now);
        for (int i = 0; i < 4; i++) {
            pair<int, int> next = { now.first + dy[i], now.second + dx[i] };
            int next_color = A[next.first][next.second];
            if (is_ok(next))
                if (Color == next_color || next_color == 0)
                    q.push(next);
        }
    }
    Block_Group.push_back({ {cnt_B, Rainbow.size()},Criterion});
    for (int i = 0; i < Rainbow.size(); i++)
        visited[Rainbow[i].first][Rainbow[i].second] = false;
    Rainbow.clear();
}
 
void Erase_Group() {
    memset(visited, false, sizeof(visited));
    pair<int, int> st = Block_Group[0].second;
    queue<pair<int, int>> q;
    q.push(st);
    int color = A[st.first][st.second];
    while (!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();
        if (visited[now.first][now.second])
            continue;
        visited[now.first][now.second] = true;
        A[now.first][now.second] = -2;
        for (int i = 0; i < 4; i++) {
            pair<int, int> next = { now.first + dy[i], now.second + dx[i] };
            int next_color = A[next.first][next.second];
            if (next_color < 0)
                continue;
            if (is_ok(next)) {
                if (color == next_color || next_color == 0)
                    q.push(next);
            }
        }
    }
    Score += (int)pow(Block_Group[0].first.first, 2);
    Block_Group.clear();
}
 
bool is_ok(pair<int, int> now) {
    if (now.first < 1 || now.first > N || now.second < 1 || now.second > N)
        return false;
    return true;
}
 
void Gravity() {
    for (int i = 1; i <= N; i++) {
        for (int j = N; j >= 1; j--) {
            if (A[j][i] < 0)
                continue;
            pair<int, int> to = { j, i};
            while (true) {
                pair<int, int> next = { to.first + 1, to.second };
                if (is_ok(next) && A[next.first][next.second] == -2)
                    to = next;
                else break;
            }
            if (to.first == j && to.second == i)
                continue;
            A[to.first][to.second] = A[j][i];
            A[j][i] = -2;
        }
    }
}
 
void Rotate() {
    int temp[MAX_N][MAX_N];
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            temp[i][j] = A[i][j];
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            A[N + 1 - j][i] = temp[i][j];
        }
    }
}