21609 상어중학교 > 2028KB, 0ms
- DFS로 품
- 푼 방법
- 블럭 찾고 (find_block())
- DFS를 통해 블럭의 크기를 찾고 가장 큰 블럭과 비교해서 갱신한다.
- 여기서 어이없게 틀렸는데 나는 블록이 2개 이상일 때만 찾는다고 하니까 블럭이 1개일 때만 고려했다. 블럭이 0개인걸 고려 안해서 39%에서 시간초과 났음
- 터지고 (boom())
- 찾은 블럭사이즈만큼 점수계산 후
- DFS를 통해 해당 블럭 -2(빈칸)으로 바꿔줌.
- 이때 DFS는 find_block()의 DFS와 같은 함수를 썼는데 flag를 이용해서 기능을 달리함
- 중력 작용 (gravity())
- 오른쪽 아래에서부터 위로 가는 방식. ↑↑↑↑ 이런 식
- 내려야 하는 블럭 찾고 쭉 내림
- 중력 작용 한 번에 해보려고 했는데 잘 안됐음
- 90도 회전 (spin())
- 90도 반시계 방향 회전 로직
- map_temp에다가 map을 저장 후 90도 회전한 map_temp를 map에 다시 복사하는 방식
- 반시계 방향 회전 로직은 [i][j]
- 중력 작용 (gravity())
- 블럭 찾고 (find_block())
=> 중력작용, DFS, 회전 기출
#include <iostream>
#include <stack>
#include <iomanip>
#include <cstring>
#define MAX 20
using namespace std;
int N, M, map[MAX][MAX] = {};
int boom_x, boom_y, boom_size, boom_rainbow;
bool visited[MAX][MAX] = {};
int result = 0;
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> map[i][j];
}
pair<int,int> DFS(int start_y, int start_x, int start_value, bool boom_flag) {
bool visited_local[MAX][MAX] = {};
int dy[4] = { -1,1,0,0 }, dx[4] = { 0,0,-1,1 };
int block_cnt = 0, rainbow = 0;
stack<pair<int, int>> s;
s.push({ start_y, start_x });
while (!s.empty()) {
int y = s.top().first, x = s.top().second; s.pop();
if (visited_local[y][x]) continue;
visited_local[y][x] = true;
if (boom_flag) map[y][x] = -2;
if (map[y][x] != 0) visited[y][x] = true;
else rainbow++;
block_cnt++;
for (int i = 0; i < 4; i++) {
int new_y = y + dy[i], new_x = x + dx[i];
if (new_y >= N || new_x >= N || new_y < 0 || new_x < 0 || map[new_y][new_x] < 0) continue;
if ((!visited_local[new_y][new_x]) && (start_value == map[new_y][new_x] || map[new_y][new_x] == 0)) {
s.push({ new_y, new_x });
}
}
}
//cout << endl << endl;
return { block_cnt,rainbow };
}
bool find_block() {
// 기준 블록 & 크기 & visited 초기화
boom_x = -1; boom_y = -1; boom_size = 0; boom_rainbow = 0;
for (int i = 0; i < N; i++) memset(visited[i], false, N);
// labeling & choose
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] <= 0 || visited[i][j]) continue;
pair<int, int> DFS_result = DFS(i, j, map[i][j], false);
if (DFS_result.first > boom_size) {
boom_y = i; boom_x = j; boom_size = DFS_result.first; boom_rainbow = DFS_result.second;
}
else if (DFS_result.first == boom_size) {
if (DFS_result.second > boom_rainbow) {
boom_y = i; boom_x = j; boom_size = DFS_result.first; boom_rainbow = DFS_result.second;
}
else if (DFS_result.second == boom_rainbow) {
if (i > boom_y) {
boom_y = i; boom_x = j; boom_size = DFS_result.first; boom_rainbow = DFS_result.second;
}
else if (i == boom_y) {
if (j > boom_x) {
boom_y = i; boom_x = j; boom_size = DFS_result.first; boom_rainbow = DFS_result.second;
}
}
}
}
}
}
// return
if (boom_size <= 1) return false;
return true;
}
void boom() {
result += boom_size * boom_size;
DFS(boom_y, boom_x, map[boom_y][boom_x], true);
}
void gravity() {
for (int j = 0; j < N; j++) {
for (int i = N - 1; i >= 0; i--) {
if (map[i][j] < 0) continue;
int next_i = i + 1; //, temp_i = i;
while (next_i < N && map[next_i][j] == -2) next_i++;
if (next_i - 1 != i) {
map[next_i - 1][j] = map[i][j];
map[i][j] = -2;
}
}
}
}
void spin() {
int map_temp[MAX][MAX] = {};
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
map_temp[i][j] = map[i][j];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
map[i][j] = map_temp[j][N - 1 - i];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
input();
while (find_block()) { // N^2 * DFS
boom(); // DFS
gravity(); // N^2 + a
spin(); // 2N^2
gravity(); // N^2 + a
}
cout << result;
}'coding > baekjoon_codingstudy' 카테고리의 다른 글
| 20061 모노미노도미노2 (0) | 2022.10.06 |
|---|---|
| 12100 2048(Easy) (0) | 2022.10.03 |
| 19238 스타트택시 (0) | 2022.10.02 |
| 13460 구슬 탈출2 (0) | 2022.10.02 |
| 14891 톱니바퀴 (골드 5) (0) | 2021.10.05 |
