Life Engineering
[BOJ 21609] 상어 중학교 (C++) 본문
https://www.acmicpc.net/problem/21609
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
struct blockGroup {
vector<pair<int, int> > members;
int num_rainbow;
pair<int, int> standard_block;
bool operator<(const blockGroup& b) const {
if (members.size() == b.members.size()) {
if (num_rainbow == b.num_rainbow) {
if (standard_block.first == b.standard_block.first) {
return standard_block.second > b.standard_block.second;
}
return standard_block.first > b.standard_block.first;
}
return num_rainbow > b.num_rainbow;
}
return members.size() > b.members.size();
}
};
int N, M;
int block[21][21];
bool check[21][21];
vector<blockGroup> groups;
int ans = 0;
void addGroup(int i, int j) {
int color = block[i][j];
vector<pair<int, int> > m;
vector<pair<int, int> > rainbow;
queue<pair<int, int> > q;
int num_rainbow = 0;
m.push_back({ i,j }); q.push({ i,j });
check[i][j] = true;
while (!q.empty()) {
pair<int, int> xy = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int nx = xy.first + dx[k];
int ny = xy.second + dy[k];
if (nx <= 0 || nx > N || ny <= 0 || ny > N)
continue;
if (block[nx][ny] == 0 && !check[nx][ny]) {
check[nx][ny] = true;
rainbow.push_back({ nx,ny });
q.push({ nx,ny });
m.push_back({ nx,ny });
num_rainbow++;
}
if (block[nx][ny] == color && !check[nx][ny]) {
check[nx][ny] = true;
q.push({ nx,ny });
m.push_back({ nx,ny });
}
}
}
if (m.size() >= 2)
groups.push_back({ m,num_rainbow,{i,j} });
for (int i = 0; i < rainbow.size(); i++) { //다른 group 도 체크 가능하도록 check 표시 풀어줌
check[rainbow[i].first][rainbow[i].second] = false;
}
}
bool searchBig() {
groups.clear();
memset(check, false, sizeof(check));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (block[i][j] >= 1 && block[i][j] <= M && !check[i][j]) {
addGroup(i, j);
}
}
}
if (groups.size() == 0)
return false;
sort(groups.begin(), groups.end());
blockGroup b = groups[0];
int score = b.members.size();
ans += (score * score);
for (int i = 0; i < b.members.size(); i++) {
int x = b.members[i].first;
int y = b.members[i].second;
block[x][y] = M + 1;
}
return true;
//sort groups & pick big group & remove that group
}
void gravity() {
for (int j = 1; j <= N; j++) {
for (int i = N-1; i >= 1; i--) {
if (block[i][j]>=0 && block[i][j]<=M) {
int row = i + 1;
bool isMove = false;
while (row <= N && block[row][j] == M + 1) {
row++;
isMove = true;
}
block[row - 1][j] = block[i][j];
if (isMove)
block[i][j] = M + 1;
}
}
}
}
void rotate() {
vector<vector<int> > v(N+1);
for (int i = 1; i <= N; i++) {
for (int j = N; j >= 1; j--) {
v[i].push_back(block[i][j]);
}
}
for (int j = 1; j <= N; j++) {
for (int i = 1; i <= N; i++) {
block[i][j] = v[j][i-1];
}
}
}
int main() {
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> block[i][j];
}
}
while (searchBig()) {
gravity();
rotate();
gravity();
}
cout << ans << "\n";
return 0;
}
오늘의 교훈: "문제를 잘읽자"
탐색(BFS)+구현 문제.
여기서 같은 블록 그룹이 되는 기준은 "임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다" && "일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다". 이다.
즉, 무지개 블록은 인접한 칸으로 이동해서 다른 모든 칸으로 이동할 수 있다면 그룹 간 공유 가능하다.
즉, 무지개 블록은 공유 가능한 요소이므로, BFS 탐색할 때 visit 표시 해주고, 다른 그룹을 다시 탐색하러 갈 때 무지개 블록에 visit 표시해 준 것을 풀어줘서 다른 그룹도 그 무지개 블록을 탐색 가능하게 만들어준다.
'Problem Solving' 카테고리의 다른 글
[BOJ 15654] N과 M(5) (C++) (0) | 2021.10.28 |
---|---|
[프로그래머스] 프린터 (C++) (0) | 2021.10.27 |
[프로그래머스] 가장 큰 수 (C++) (0) | 2021.10.21 |
[프로그래머스] 카펫 (C++) (0) | 2021.10.21 |
[프로그래머스] 위장 (Python3) (0) | 2021.10.21 |