https://www.acmicpc.net/problem/21609
21609번: 상어 중학교
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록
www.acmicpc.net
상당히 더러웠던 문제.
문제 자체는 어렵지 않다. 하지만 시키는게 많다, 터트리고, 중력, 돌리고, 중력...
코드의 흐름은 다음과 같다.
init() 에서는 빠른 입력을 위한 것
input() 도 그냥 입력 받는다. 딱히 특별한게 없다.
solve() 함수 에서 부터 문제 풀이를 시작한다.
find_block_group()을 돌린다, 이 함수는 false가 return되면 오토플레이가 끝나게 해놨다.
find_block_group에서는 블록그룹을 찾고, 터트려야하는 것을 판별, 그다음은 터트리는 것 까지 구현했다.
우선 memset을 이용해 check 함수, 즉 방문여부를 확인 하는 것을 false로 초기화 하였다.
맵 크기가 21*21이라 크지 않아서 해도 시간초과에 상관없을거같다.
이중 포문과 bfs를 통해서 블록 그룹을 찾는다. 이때 0도아니고, -1도 아니고 -2(빈칸)도 아니여야 한다.
그리고 check배열이 false여야 한다.
|
1
2
3
4
5
6
7
8
|
struct block {
deque<pair<int, int>> Rainbow_block;
deque<pair<int, int>> Base_block;
int total_size;
int base_block_x;
int base_block_y;
int base_color;
};
|
cs |
이때 다음과 같은 block 그룹 함수를 사용 했다. 블럭의 색, 기준블럭의 좌표, 무지개랑 기준블럭을 저장하는 deque.
그 다음에는 bfs로 탐색한다. base_color가 같은것, 그리고 무지개 블록, bfs는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
void bfs(const int& i, const int& j) {
block temp;
queue<pair<int, int>> q;
// 색깔지정 및 탐색 준비
temp.base_color = MAP[i][j];
temp.total_size = 0;
temp.base_block_x = i;
temp.base_block_y = j;
check[i][j] = true;
q.push(make_pair(i, j));
// 베이스 블럭이 당연히 맨 처음시작하는 곳 아닌가? 라고 생각
// 위에서 부터 시작하니
// 탐색 시작
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (MAP[x][y] == temp.base_color) {
temp.Base_block.push_back(make_pair(x, y));
temp.total_size++;
}
else if (MAP[x][y] == 0) {
temp.Rainbow_block.push_back(make_pair(x, y));
temp.total_size++;
}
for (int index = 0; index < 4; index++) {
int next_x = x + dx[index];
int next_y = y + dy[index];
if (check_range(next_x, next_y) && check[next_x][next_y] == false) {
if (MAP[next_x][next_y] == temp.base_color || MAP[next_x][next_y] == 0) {
check[next_x][next_y] = true;
q.push(make_pair(next_x, next_y));
}
}
}
}
// 탐색 종료 후 정리
for (auto i : temp.Rainbow_block)
check[i.first][i.second] = false;
if (temp.total_size < 2)
return;
block_group.push_back(temp);
}
|
cs |
평범한 bfs지만, 색블럭 저장, 무지개 블럭 저장하는 과정만 추가. 그리고 탐색이 끝난 뒤에는 다음과 같이
check 배열에서 rainbow_block들은 다시 false로 처리 해야한다. 왜냐하면 다른 블록 그룹도 무지개 블록을 가질 수
있기때문이다.
그리고 만약 size가 2보다 작으면 그냥 return, 문제조건이다,
block_group에 push_back해준다.
이 과정을 거치면 모든 block_group을 찾을 수 있다. 그러면 문제의 조건에 맞춰서 터트릴 block을 선정해야한다.
나는 정렬을 사용했다 . 다음과 같은 cmp함수를 만들었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
bool cmp(const block& x, const block& y) {
if (x.total_size != y.total_size)
return x.total_size > y.total_size;
else {
if (x.Rainbow_block.size() != y.Rainbow_block.size())
return x.Rainbow_block.size() > y.Rainbow_block.size();
else {
if (x.base_block_x != y.base_block_x)
return x.base_block_x > y.base_block_x;
else
return x.base_block_y > y.base_block_y;
}
}
}
|
cs |
뭐 그냥 그렇다. 처음 조건 size가 큰것, 그 다음은 무지개 블럭 사이즈가 큰거, 그 다음은 기준블럭의 행, 그 다음은 기준블럭의 열.
그러면 터트려야 하는 것이 0번 인덱스로 온다.
그리고 나면 뭐 deque에 있는 터트리는 블럭 좌표를 pop하고, 더해주면 끝이다.
그 다음은 중력,
중력은 별거없다. 맨 아래줄부터 아래가 뭔지 check하면서 내려오면된다.
반시계방향도 별거 없다. 기존에 1열이 -> 5행, 2열 ->4행,... 5열->1행으로 가는 것만 알면된다.
그리고 코드를 반복하면 끝이다. 전체코드는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
// 백준 21609 상어 중학교
#include <iostream>
#include <queue>
#include <deque>
#include <utility>
#include <iomanip>
#include <cstring>
#include <algorithm>
#define MAX 20+1
using namespace std;
struct block {
deque<pair<int, int>> Rainbow_block;
deque<pair<int, int>> Base_block;
int total_size;
int base_block_x;
int base_block_y;
int base_color;
};
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int N, M;
int MAP[MAX][MAX];
bool check[MAX][MAX] = { false };
deque<block> block_group;
int result_point = 0;
void reverse_clock_wise() {
// 시계방향으로 돌리면 1열 2열 3열 4열 5열 -> 5행 4행 3행 2행 1행
queue<int> q;
for (int j = 1; j <= N; j++)
for (int i = 1; i <= N; i++)
q.push(MAP[i][j]);
for (int i = N; i >= 1; i--) {
for (int j = 1; j <= N; j++) {
MAP[i][j] = q.front();
q.pop();
}
}
}
void Gravity() {
// 내려가는 방향은 1번 인덱스
for (int i = N - 1; i >= 1; i--) {
for (int j = 1; j <= N; j++) {
if (MAP[i][j] == -1 || MAP[i][j] == -2)
continue;
int num = MAP[i][j];
MAP[i][j] = -2;
int prev_x = i;
prev_x++;
while (prev_x <= N) {
if (MAP[prev_x][j] != -2)
break;
prev_x++;
}
prev_x--;
MAP[prev_x][j] = num;
}
}
}
bool cmp(const block& x, const block& y) {
if (x.total_size != y.total_size)
return x.total_size > y.total_size;
else {
if (x.Rainbow_block.size() != y.Rainbow_block.size())
return x.Rainbow_block.size() > y.Rainbow_block.size();
else {
if (x.base_block_x != y.base_block_x)
return x.base_block_x > y.base_block_x;
else
return x.base_block_y > y.base_block_y;
}
}
}
bool check_range(const int& next_x, const int& next_y) {
if (next_x >= 1 && next_y >= 1 && next_x <= N && next_y <= N)
return true;
else
return false;
}
void bfs(const int& i, const int& j) {
block temp;
queue<pair<int, int>> q;
// 색깔지정 및 탐색 준비
temp.base_color = MAP[i][j];
temp.total_size = 0;
temp.base_block_x = i;
temp.base_block_y = j;
check[i][j] = true;
q.push(make_pair(i, j));
// 베이스 블럭이 당연히 맨 처음시작하는 곳 아닌가? 라고 생각
// 위에서 부터 시작하니
// 탐색 시작
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (MAP[x][y] == temp.base_color) {
temp.Base_block.push_back(make_pair(x, y));
temp.total_size++;
}
else if (MAP[x][y] == 0) {
temp.Rainbow_block.push_back(make_pair(x, y));
temp.total_size++;
}
for (int index = 0; index < 4; index++) {
int next_x = x + dx[index];
int next_y = y + dy[index];
if (check_range(next_x, next_y) && check[next_x][next_y] == false) {
if (MAP[next_x][next_y] == temp.base_color || MAP[next_x][next_y] == 0) {
check[next_x][next_y] = true;
q.push(make_pair(next_x, next_y));
}
}
}
}
// 탐색 종료 후 정리
for (auto i : temp.Rainbow_block)
check[i.first][i.second] = false;
if (temp.total_size < 2)
return;
block_group.push_back(temp);
}
bool find_block_group() {
// 블록 그룹 먼저 찾기
memset(check, false, sizeof(check));
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
if (MAP[i][j] != 0 && MAP[i][j] != -1 && MAP[i][j] != -2 && check[i][j] == false)
bfs(i, j);
if (block_group.empty())
return false;
sort(block_group.begin(), block_group.end(), cmp);
// block 터트리기 -2 는 빈칸
result_point += block_group[0].total_size * block_group[0].total_size;
for (auto i : block_group[0].Rainbow_block)
MAP[i.first][i.second] = -2;
for (auto i : block_group[0].Base_block)
MAP[i.first][i.second] = -2;
block_group.clear();
return true;
}
void solve() {
for (;;) {
if (find_block_group() == false)
return;
Gravity();
reverse_clock_wise();
Gravity();
}
}
void input() {
cin >> N >> M;
// (-1,검은색),(0,무지개),그리고 나머지 M까지 색
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
cin >> MAP[i][j];
}
void init() {
ios::sync_with_stdio(false);
cin.tie(0);
}
int main() {
init();
input();
solve();
cout << result_point << endl;
}
|
cs |
'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글
| [백준 21611] 마법사 상어와 블리자드 (C++) (0) | 2021.08.26 |
|---|---|
| [백준 20061] 모노미노도미노 2 (C++) (0) | 2021.08.23 |
| [백준 14499] 주사위 굴리기 (C++) (0) | 2021.08.21 |
| [백준 3190] 뱀 (C++) (0) | 2021.08.21 |
| [백준 1092] 배 (C++) (0) | 2021.08.21 |