BOJ 21609, 상어중학교
Source: BOJ 21609 상어중학교
상어 중학교
체감상 백준 문제를 풀면서 가장 난이도가 높았던 문제였다..
문제를 요약해 보자면 N X N인 격자의 모든 칸에 블록이 있고, 검은색 블록, 무지개 블록, 일반 블록이 있다.
검은색 블록은 -1, 무지개 블록은 0, 일반 블록은 1~M의 자연수로 표현한다
블록그룹은 검은색 블록은 포함X, 무지개 블록은 여러개 포함할 수 있고, 일반 블록은 같은 수만 포함 할 수 있다.
- 크기가 가장 큰 블록 그룹을 찾는다.
(무지개 블록 수 > 기준블록의 행 > 기준블록의 열)
- 찾은 블록 그룹을 제거, 블록의 수의 제곱 만큼 점수 얻기
- 중력작용
- 반시계방향으로 90도 회전
- 중력작용
블록 그룹의 크기가 2이상인 경우 계속 반복
가장 크기가 큰 블록을 찾기 위해서 BLOCK이라는 구조체를 선언하고 블록그룹의 크기, 기준블록의 위치, 무지개 블록의 수, 블록형상 저장을 위한 벡터를 만들어 관리하였다.
struct BLOCK{
int Size;
int x, y;
int Rainbow_Cnt;
vector<pair<int, int>> Block_Group;
}
중요하게 착안해야 할 부분은 1번 크기가 가장 큰 블록 그룹을 찾을 때 BFS를 이용하여 찾아야 하고, 무지개블록은 중복탐색을 허용해야 한다.
따라서, Visit[MAX][MAX]와 R_Visit[MAX][MAX]를 따로 선언하여 BFS와 Find_Largest_Block함수에서 중복을 따로 설정해주어야 한다.
BFS에서 찾은 블록 그룹과 Find_Largest_Block함수에서의 그룹중 1번을 만족하는 것을 찾아 계속 최신화 한다.
찾은 블록그룹에 Gravity(), Rotate()함수를 적용하고 조건에 만족할때 까지 반복한다.
//검은색 블록을 만나기 전까지 아래로 내리는 함수
void Gravity(){
for (int i = N - 2; i >= 0; i--)
{
for (int j = 0; j < N; j++)
{
if (board[i][j] == -2) continue;
if (board[i][j] == -1) continue;
int Color = board[i][j];
int nx = i + 1;
while (1)
{
if (board[nx][j] != -2) break;
if (nx == N) break;
nx++;
}
nx--;
board[i][j] = -2;
board[nx][j] = Color;
}
}
}
//반시계 방향으로 90도 회전시키는 함수
void Rotate(){
for (int i = 0; i < N / 2; i++)
{
int Sx = i;
int Sy = i;
int Ex = N - i - 1;
int Ey = N - i - 1;
int x_Idx = Ex;
int y_Idx = Sy;
int Idx = 0;
vector<int> Temp;
for (int x = Ex; x > Sx; x--) Temp.push_back(board[x][Sy]);
for (int y = Sy; y < Ey; y++) board[x_Idx--][Sy] = board[Sx][y];
for (int x = Sx; x < Ex; x++) board[Sx][y_Idx++] = board[x][Ey];
for (int y = Ey; y > Sy; y--) board[x_Idx++][Ey] = board[Ex][y];
for (int y = Ey; y > Sy; y--) board[Ex][y] = Temp[Idx++];
}
}
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define MAX 25
#define NVALUE -2
int N, M;
int board[MAX][MAX];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool Visit[MAX][MAX];
bool R_Visit[MAX][MAX];
int answer;
struct BLOCK{
int Size;
int x, y;
int Rainbow_Cnt;
vector<pair<int, int>> Block_Group;
};
bool cmp(pair<int, int> A, pair<int, int> B){
if(A.first <= B.first){
if(A.first == B.first){
if(A.second < B.second){
return true;
}
return false;
}
return true;
}
return false;
}
bool Comp_Block(BLOCK A, BLOCK B){
if(A.Size >= B.Size){
if(A.Size == B.Size){
if(A.Rainbow_Cnt >= B.Rainbow_Cnt){
if(A.Rainbow_Cnt == B.Rainbow_Cnt){
if(A.x >= B.x){
if(A.x == B.x){
if(A.y > B.y){
return true;
}
return false;
}
return true;
}
return false;
}
return true;
}
return false;
}
return true;
}
return false;
}
BLOCK BFS(int a, int b, int Color){
memset(R_Visit, false, sizeof(R_Visit));
queue<pair<int, int>> Q;
vector<pair<int, int>> Block;
vector<pair<int, int>> Except_Rainbow_Block;
Q.push({a, b});
Block.push_back({a, b});
Except_Rainbow_Block.push_back({a, b});
Visit[a][b] = true;
int Rainbow = 0;
while(!Q.empty()){
auto cur = Q.front();
int x = cur.X;
int y = cur.Y;
Q.pop();
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < N)
{
if (board[nx][ny] == 0)
{
if (R_Visit[nx][ny] == false)
{
R_Visit[nx][ny] = true;
Rainbow++;
Block.push_back(make_pair(nx, ny));
Q.push(make_pair(nx, ny));
}
}
else if(board[nx][ny] == Color)
{
if (Visit[nx][ny] == false)
{
Visit[nx][ny] = true;
Q.push(make_pair(nx, ny));
Block.push_back(make_pair(nx, ny));
Except_Rainbow_Block.push_back(make_pair(nx, ny));
}
}
}
}
}
sort(Except_Rainbow_Block.begin(), Except_Rainbow_Block.end(), cmp);
BLOCK R_Block;
R_Block.Size = Block.size();
R_Block.Rainbow_Cnt = Rainbow;
R_Block.x = Except_Rainbow_Block[0].X;
R_Block.y = Except_Rainbow_Block[0].Y;
R_Block.Block_Group = Block;
return R_Block;
}
BLOCK Find_Largest_Block(){
memset(Visit, false, sizeof(Visit));
BLOCK Result;
Result.Size = -1;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(Visit[i][j]) continue;
if(board[i][j] == -1 || board[i][j] == 0 || board[i][j] == NVALUE) continue;
BLOCK Temp_Block = BFS(i, j, board[i][j]);
if(Result.Size == -1){
Result = Temp_Block;
}
else{
if(Comp_Block(Temp_Block, Result)){
Result = Temp_Block;
}
}
}
}
return Result;
}
void Delete_Block(BLOCK A){
vector<pair<int, int>> v = A.Block_Group;
for(int i=0; i<v.size(); i++){
int x = v[i].X;
int y = v[i].Y;
board[x][y] = NVALUE;
}
answer += (v.size() * v.size());
}
void Gravity(){
for (int i = N - 2; i >= 0; i--)
{
for (int j = 0; j < N; j++)
{
if (board[i][j] == -2) continue;
if (board[i][j] == -1) continue;
int Color = board[i][j];
int nx = i + 1;
while (1)
{
if (board[nx][j] != -2) break;
if (nx == N) break;
nx++;
}
nx--;
board[i][j] = -2;
board[nx][j] = Color;
}
}
}
void Rotate(){
for (int i = 0; i < N / 2; i++)
{
int Sx = i;
int Sy = i;
int Ex = N - i - 1;
int Ey = N - i - 1;
int x_Idx = Ex;
int y_Idx = Sy;
int Idx = 0;
vector<int> Temp;
for (int x = Ex; x > Sx; x--) Temp.push_back(board[x][Sy]);
for (int y = Sy; y < Ey; y++) board[x_Idx--][Sy] = board[Sx][y];
for (int x = Sx; x < Ex; x++) board[Sx][y_Idx++] = board[x][Ey];
for (int y = Ey; y > Sy; y--) board[x_Idx++][Ey] = board[Ex][y];
for (int y = Ey; y > Sy; y--) board[Ex][y] = Temp[Idx++];
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>N>>M;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
cin>>board[i][j];
}
}
while(1){
BLOCK target = Find_Largest_Block();
if(target.Size < 2) break;
Delete_Block(target);
Gravity();
Rotate();
Gravity();
}
cout<<answer;
return 0;
}
Leave a comment