💡Solution & Idea
- 이 문제는 크게
1. 블록을 만드는 부분 2. 중력이 작용하는 부분 3. 격자를 90도 반시계 방향으로 회전하는 부분으로 나눌 수 있다 - 여러 개의 블록으로 나눌 때 주의해야 할 점은, 무지개 블록은 여러 블록에 포함 될 수 있다는 것이다.
예를 들어, 다음과 같은 경우에 이 블록은 두 개의 경우로 나눌 수 있다
Initialize & Compare 함수
- 여러 개의 블록을 관리하기 위해 구조체를 선언
- 해당 블록 안에 있는 멤버들의 좌표를 저장하는 벡터, 블록의 크기, 무지개 색의 개수, 시작점
struct BLOCK {
vector<pair<int, int>> v;
int blockSize;
int rainbow;
pair<int, int> start;
};
vector<BLOCK> block;- 블록 간 우선 순위를 나타내기 위해 compare 함수 정의
bool compare(const BLOCK& A, const BLOCK& B) {
if (A.blockSize == B.blockSize)
if (A.rainbow == B.rainbow)
if (A.start.first == B.start.first)
return A.start.second > B.start.second;
else return A.start.first > B.start.first;
else return A.rainbow > B.rainbow;
else return A.blockSize > B.blockSize;
}1. Make Block
- 기본적으로 BFS, 너비 우선 탐색을 이용해 하나의 블록을 만드는데, 전체 좌표를 탐색하다가 1~M 사이의 숫자가 나오면 이 지점을 블록의 시작점으로 둔다
visited, r_visited두 개를 두어, 무지개 지점을 방문 했을 때는r_visited에 방문 표시를 해주고 이번 한 블록을 만들고 나면 다시 초기화 된다 (다른 블록을 만들 때도 다시 방문할 수 있기 때문에)- 무지개 지점이 아닌 같은 숫자를 방문 했을 때는
visited에 방문 표시를 해준다 - 탐색이 끝난 후, 블록의 크기가 2보다 작은 경우 (즉, 1인 경우)
block을 비워준다
void makeBlock(int i, int j, int colour) {
memset(r_visited, false, sizeof(r_visited));
visited[i][j] = true;
queue<pair<int, int>> q;
q.push({ i,j });
block[blockNum].blockSize++;
block[blockNum].v.push_back({ i,j });
block[blockNum].start.first = i;
block[blockNum].start.second = j;
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
if (map[ny][nx] == BLACK) continue;
if (map[ny][nx] == RAINBOW && !r_visited[ny][nx]) {
r_visited[ny][nx] = true;
block[blockNum].rainbow++;
block[blockNum].blockSize++;
block[blockNum].v.push_back({ ny, nx });
q.push({ ny, nx });
}
else if (map[ny][nx] == colour && !visited[ny][nx]) {
visited[ny][nx] = true;
block[blockNum].blockSize++;
block[blockNum].v.push_back({ ny, nx });
q.push({ ny, nx });
}
}
}
if (block[blockNum].blockSize ==1) {
visited[i][j] = false;
block[blockNum].v.clear();
block[blockNum].blockSize = 0;
block[blockNum].rainbow = 0;
block[blockNum].start.first = 0;
block[blockNum].start.second = 0;
return;
}
blockNum++;
}2. Move Down - Gravity
- N-2번째 행부터 아래로 움직일 수 있는지 탐색해본다
- 현재 칸이 빈 칸이거나, 검은색 칸이면 움직이지 않는다
- 아래 칸이 다음 칸이 빈칸이 아닐 때까지 움직여준다
void moveDown() {
for (int y = N - 2; y >= 0; y--) {
for (int x = 0; x < N; x++) {
if (map[y][x] == EMPTY || map[y][x]==BLACK) continue;
int ny = y;
while (ny<N-1 && map[ny+1][x]==EMPTY)
ny++;
if (ny != y) {
map[ny][x] = map[y][x];
map[y][x] = EMPTY;
}
}
}
}3. Rotate
- 격자를 회전하는 부분은 이제 그냥 암기
- 반시계 방향 90도 회전
void rotate() {
int tmp[MAX][MAX];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
tmp[i][j] = map[i][j];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
map[i][j] = tmp[j][N - 1 - i];
}- 시계 방향 90도 회전
void rotate() {
int tmp[MAX][MAX];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
tmp[i][j] = map[i][j];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
map[i][j] = tmp[N-i-j][i];
}Source Code
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
const int MAX = 21;
const int EMPTY = -2;
const int BLACK = -1;
const int RAINBOW = 0;
const int dy[] = { 1,-1,0,0 };
const int dx[] = { 0,0,1,-1 };
using namespace std;
struct BLOCK {
vector<pair<int, int>> v;
int blockSize;
int rainbow;
pair<int, int> start;
};
vector<BLOCK> block;
int ret = 0;
int N, M, blockNum=0;
vector<vector<int>> map;
bool visited[MAX][MAX], r_visited[MAX][MAX];
bool compare(const BLOCK& A, const BLOCK& B) {
if (A.blockSize == B.blockSize)
if (A.rainbow == B.rainbow)
if (A.start.first == B.start.first)
return A.start.second > B.start.second;
else return A.start.first > B.start.first;
else return A.rainbow > B.rainbow;
else return A.blockSize > B.blockSize;
}
void input() {
cin >> N >> M;
map = vector<vector<int>>(N, vector<int>(N));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> map[i][j];
block = vector<BLOCK>(MAX * MAX / 2);
}
void init() {
memset(visited, 0, sizeof(visited));
for (int i = 0; i < blockNum; i++) {
block[i].v.clear();
block[i].blockSize = 0;
block[i].rainbow = 0;
block[i].start.first = 0;
block[i].start.second = 0;
}
blockNum = 0;
}
void makeBlock(int i, int j, int colour) {
memset(r_visited, false, sizeof(r_visited));
visited[i][j] = true;
queue<pair<int, int>> q;
q.push({ i,j });
block[blockNum].blockSize++;
block[blockNum].v.push_back({ i,j });
block[blockNum].start.first = i;
block[blockNum].start.second = j;
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
if (map[ny][nx] == BLACK) continue;
if (map[ny][nx] == RAINBOW && !r_visited[ny][nx]) {
r_visited[ny][nx] = true;
block[blockNum].rainbow++;
block[blockNum].blockSize++;
block[blockNum].v.push_back({ ny, nx });
q.push({ ny, nx });
}
else if (map[ny][nx] == colour && !visited[ny][nx]) {
visited[ny][nx] = true;
block[blockNum].blockSize++;
block[blockNum].v.push_back({ ny, nx });
q.push({ ny, nx });
}
}
}
if (block[blockNum].blockSize ==1) {
visited[i][j] = false;
block[blockNum].v.clear();
block[blockNum].blockSize = 0;
block[blockNum].rainbow = 0;
block[blockNum].start.first = 0;
block[blockNum].start.second = 0;
return;
}
blockNum++;
}
void rotate() {
int tmp[MAX][MAX];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
tmp[i][j] = map[i][j];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
map[i][j] = tmp[j][N - 1 - i];
}
void moveDown() {
for (int y = N - 2; y >= 0; y--) {
for (int x = 0; x < N; x++) {
if (map[y][x] == EMPTY || map[y][x]==BLACK) continue;
int ny = y;
while (ny<N-1 && map[ny+1][x]==EMPTY)
ny++;
if (ny != y) {
map[ny][x] = map[y][x];
map[y][x] = EMPTY;
}
}
}
}
void getScore() {
ret += (block[0].blockSize * block[0].blockSize);
for (int i = 0; i < block[0].v.size(); i++) {
int y = block[0].v[i].first;
int x = block[0].v[i].second;
map[y][x] = EMPTY;
}
}
void solution() {
while (true) {
init();
for (int i = 0; i< N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] >= 1 && map[i][j] <= M && !visited[i][j])
makeBlock(i, j, map[i][j]);
}
}
if (blockNum == 0) break;
sort(block.begin(),block.end(), compare);
getScore();
moveDown();
rotate();
moveDown();
}
}
int main() {
input();
solution();
cout << ret << endl;
return 0;
}
Born to be happy, Not perfect 🤍