21609 상어중학교

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())

 

=> 중력작용, 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;
}