알고리즘 모음(C++)
백준 21609 - 상어 중학교(C++) 본문
문제 링크입니다. https://www.acmicpc.net/problem/21609
21609번: 상어 중학교
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록
www.acmicpc.net
삼성 SW 역량테스트 기출 문제였습니다.
그래프 탐색 + 구현 문제로 구현해야할 것이 많은 문제였습니다.
한 일반 블록에서 상하좌우로 접한 블록 그룹을 찾은 뒤, 조건에 따라 정렬을 합니다.
이때 블록 그룹에는 무지개 블록은 항상 포함 가능합니다.
크기 -> 무지개 블록 수 -> 기준 블록의 행 -> 기준 블록의 열 순으로 블록 그룹을 정렬하고 가장 큰 그룹을 제거합니다.
블록을 제거했으니, 빈칸이 생겼으므로 중력을 통해 남은 블록을 밑으로 내리고, 90도 회전시킨뒤, 중력을 작용합니다.
이 과정을 그룹이 생기지 않을 때까지 반복하면 되는 문제였습니다.
이 문제를 풀기 위해서는 생각해야할 것이 있습니다.
1. 다른 블록 그룹들을 만들 때, 같은 무지개 블록은 계속 포함될 수 있어야한다.
2. 크기 -> 무지개 블록 수 -> 기준 블록의 행 -> 기준 블록의 열 순으로 정렬을 해야한다.
3. 빈칸을 어떻게 만들 것인가.
4. 중력 작용 과정을 어떻게 구현할 것인가.
5. 90도 회전 과정을 어떻게 구현할 것인가.
1. 다른 블록 그룹을 만들 때, 같은 무지개 블록을 어떻게 포함시킬 것인가?
void Find_group(int x) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
block information = { 0,0,0,0 };
if (check[i][j] == 0 && map[i][j] == x) {
information = bfs(i,j,x);
}
if (information.cnt_block >= 2) {
blocks.push_back(information);
}
reset_rainbow();
}
}
memset(check, 0, sizeof(check));
}저는 무지개 블록과 X 색깔을 가진 블록 그룹을 찾았습니다. 그 뒤, 무지개 블록만 check 배열을 0으로 만들었습니다.
블록 그룹을 찾을 때, 기준 블록을 정해야합니다.
기준 블록의 경우, 행의 값이 작은 것 -> 열의 값이 작을 것 순으로 정렬을 해주면 됩니다.
2. 블록 그룹의 정렬
typedef struct block {
int cnt_block;
int cnt_rainbow;
int x;
int y;
}block;
/////////////////////////////////////////////
bool cmp2(block a, block b) {
if (a.cnt_block > b.cnt_block) return true;
else if (a.cnt_block == b.cnt_block) {
if (a.cnt_rainbow > b.cnt_rainbow) return true;
else if (a.cnt_rainbow == b.cnt_rainbow) {
if (a.x > b.x) return true;
else if (a.x == b.x) {
if (a.y > b.y) return true;
else return false;
}
else return false;
}
else return false;
}
else return false;
}구조체 block의 경우, 블록 그룹의 크기, 무지개 블록이 갯수, 기준 블록의 행렬을 저장합니다.
우선 순위에 따라서 정렬 기준을 세워준 뒤, sort를 해주면 됩니다.
3. 빈칸을 어떻게 만들 것인가?
void Erase_blocks() {
queue<qu> q;
q.push({ blocks[0].x, blocks[0].y, map[blocks[0].x][blocks[0].y] });
check[blocks[0].x][blocks[0].y];
while (!q.empty()) {
int x = q.front().x;
int y = q.front().y;
int col = q.front().color;
q.pop();
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx >= 1 && yy >= 1 && xx <= N && yy <= N) {
if ((map[xx][yy] == col || map[xx][yy] == 0)&& check[xx][yy] == 0) {
check[xx][yy] = 1;
map[xx][yy] = 9;
q.push({ xx,yy,col });
}
}
}
}
memset(check, 0, sizeof(check));
}정렬을 통해 지워야할 그룹을 찾았습니다. 그룹의 정보에는 기준 블록의 위치가 저장되어 있으므로
해당 위치를 바탕으로 상하좌우 BFS를 통해 그룹을 다시 찾았습니다. 그 후, 해당 블록들을 모두 9로 바꿔줌으로
빈칸임을 표시했습니다.
4. 중력 작용의 구현
void gravity(){
for (int j = 1; j <= N; j++) {
for (int i = N; i >= 1; i--) {
if (map[i][j] >= 0 && map[i][j] <= M ) {
int x = i;
int y = j;
int num = map[i][j];
map[i][j] = 9;
while (1) {
if (x == N && map[N][y] == 9) {
map[x][y] = num;
break;
}
else if (map[x][y] == -1 || (map[x][y] >= 0 && map[x][y] <= M)) {
map[x - 1][y] = num;
break;
}
x++;
}
}
}
}
}중력의 경우, 열은 그대로지만 행은 변합니다. 따라서 행을 +1 해주면서 아래로 내려주면 됩니다.
블록을 더 이상 내릴 수 없는 경우는 끝에 도달했거나, 다른 블록이 있거나, 검은색 블록이 있을 때입니다.
이 경우에는 블록을 더 이상 내리지 않고 해당 칸에 저장해줍니다.
저의 경우, 행의 아래부분부터 내리기 시작했기에, 다른 블록이 있는 경우가 존재합니다. 상황에 따라 조건을 바꿔주면 됩니다.
5. 90도 회전 과정의 구현
void Reverse_90() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
reverse_map[N - j + 1][i] = map[i][j];
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
map[i][j] = reverse_map[i][j];
}
}
}
90도 회전 과정을 살펴보겠습니다.
(1 , 3)에 있던 -1이 (3 , 1)로 이동했습니다.
(1 , 4)에 있던 3이 (2, 1)로 이동했습니다.
(2 , 5)에 있던 -1이 (1 , 2)로 이동했습니다.
(3 , 4)에 있던 1이 (2 , 3)으로 이동했습니다.
해당 과정에서 공통점은, (x , y) -> (k , x)로 이동했다는 점입니다.
또한 y + k는 값이 6으로 계속 동일했습니다.
즉, (X , Y)에서 90도를 이동한다면, (N+1 - Y , X)로 이동함을 알 수 있습니다.
1 ~ 5번 과정을 전부 구현했다면 전부 합쳐주면 문제를 풀 수 있습니다.
문제 접근 방법
1. 블록 그룹을 찾는다.
2. 블록 그룹 중 기준에 맞는 그룹을 찾는다.
3. 해당 그룹을 없앤다.
4. 중력을 작용한다.
5. 90도 회전을 한다.
6. 다시 중력을 작용한다.
7. 1 ~ 6 과정을 블록 그룹이 더 이상 만들어지지 않을 때까지 반복한다.
8. 해당 과정을 반복하면서 (없어진 그룹의 블록 수^2)의 합을 구한다.
자세한 것은 코드를 참고해주세요.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
int map[21][21];
int reverse_map[21][21];
int check[21][21];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int N, M;
int ans;
typedef struct qu {
int x;
int y;
int color;
}qu;
typedef struct block {
int cnt_block;
int cnt_rainbow;
int x;
int y;
}block;
vector<block> blocks;
bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first < b.first) return true;
else if (a.first == b.first) {
if (a.second < b.second) return true;
else return false;
}
else return false;
}
bool cmp2(block a, block b) {
if (a.cnt_block > b.cnt_block) return true;
else if (a.cnt_block == b.cnt_block) {
if (a.cnt_rainbow > b.cnt_rainbow) return true;
else if (a.cnt_rainbow == b.cnt_rainbow) {
if (a.x > b.x) return true;
else if (a.x == b.x) {
if (a.y > b.y) return true;
else return false;
}
else return false;
}
else return false;
}
else return false;
}
block bfs(int x, int y, int color) {
vector<pair<int, int>> block_;
block information = { 1,0,0,0 };
queue<qu> q;
q.push({ x,y,color });
check[x][y] = 1;
block_.push_back(make_pair(x, y));
while (!q.empty()) {
int x1 = q.front().x;
int y1 = q.front().y;
int col = q.front().color;
q.pop();
for (int i = 0; i < 4; i++) {
int xx = x1 + dx[i];
int yy = y1 + dy[i];
if (xx >= 1 && yy >= 1 && xx <= N && yy <= N) {
if ((map[xx][yy] == col || map[xx][yy] == 0) && check[xx][yy] == 0 ) {
if (map[xx][yy] == 0) {
information.cnt_block++;
information.cnt_rainbow++;
check[xx][yy] = 1;
q.push({ xx,yy,col });
}
else {
information.cnt_block++;
block_.push_back(make_pair(xx, yy));
check[xx][yy] = 1;
q.push({ xx,yy,col });
}
}
}
}
}
sort(block_.begin(), block_.end(), cmp);
information.x = block_[0].first;
information.y = block_[0].second;
return information;
}
void reset_rainbow() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (map[i][j] == 0 && check[i][j] == 1) {
check[i][j] = 0;
}
}
}
}
void Find_group(int x) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
block information = { 0,0,0,0 };
if (check[i][j] == 0 && map[i][j] == x) {
information = bfs(i,j,x);
}
if (information.cnt_block >= 2) {
blocks.push_back(information);
}
reset_rainbow();
}
}
memset(check, 0, sizeof(check));
}
void Erase_blocks() {
queue<qu> q;
q.push({ blocks[0].x, blocks[0].y, map[blocks[0].x][blocks[0].y] });
check[blocks[0].x][blocks[0].y];
while (!q.empty()) {
int x = q.front().x;
int y = q.front().y;
int col = q.front().color;
q.pop();
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx >= 1 && yy >= 1 && xx <= N && yy <= N) {
if ((map[xx][yy] == col || map[xx][yy] == 0)&& check[xx][yy] == 0) {
check[xx][yy] = 1;
map[xx][yy] = 9;
q.push({ xx,yy,col });
}
}
}
}
memset(check, 0, sizeof(check));
}
void gravity(){
for (int j = 1; j <= N; j++) {
for (int i = N; i >= 1; i--) {
if (map[i][j] >= 0 && map[i][j] <= M ) {
int x = i;
int y = j;
int num = map[i][j];
map[i][j] = 9;
while (1) {
if (x == N && map[N][y] == 9) {
map[x][y] = num;
break;
}
else if (map[x][y] == -1 || (map[x][y] >= 0 && map[x][y] <= M)) {
map[x - 1][y] = num;
break;
}
x++;
}
}
}
}
}
void Reverse_90() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
reverse_map[N - j + 1][i] = map[i][j];
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
map[i][j] = reverse_map[i][j];
}
}
}
void solve() {
while (1) {
for (int i = 1; i <= M; i++) {
Find_group(i);
}
if (blocks.size() == 0) break;
sort(blocks.begin(), blocks.end(), cmp2);
Erase_blocks();
ans += (blocks[0].cnt_block * blocks[0].cnt_block);
gravity();
Reverse_90();
gravity();
blocks.clear();
}
cout << ans;
}
int main() {
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> map[i][j];
}
}
solve();
return 0;
}
질문 및 조언 댓글 남겨주세요
'백준' 카테고리의 다른 글
| 백준 11559 - Puyo Puyo(C++) (0) | 2021.12.28 |
|---|---|
| 백준 20056 - 마법사 상어와 파이어볼(C++) (0) | 2021.12.26 |
| 백준 15683 - 감시(C++) (0) | 2021.12.20 |
| 백준 16933 - 벽 부수고 이동하기 3(C++) (0) | 2021.11.20 |
| 백준 17219 - 비밀번호 찾기(C++) (0) | 2021.11.19 |
