[백준/BOJ] 백준 21609번 : 상어 중학교

https://www.acmicpc.net/problem/21609

21609번: 상어 중학교

그룹을 dfs를 통해 확인하면서 확인이 끝나면 해당 그룹의 블록 개수와 무지개 블록의 개수를 반환하는 함수를 만들었고, 블록을 지우는 함수, 중력을 작용하는 함수, 90도 반시계 방향 회전하는 함수를 만들어서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int n, m;
int board[20][20];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
long long result = 0;

//dfs를 통해 블록을 지운다
void Erase(pair<int, int> here, int color, vector<vector<int>>& erased)
{
	//빈 블록은 -2로 표시
	board[here.first][here.second] = -2;

	//지운 위치 체크
	erased[here.first][here.second] = 1;

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && erased[there.first][there.second] == 0 && (board[there.first][there.second] == 0 || board[there.first][there.second] == color))
		{
			Erase(there, color, erased);
		}
	}
}

//탐색이 끝나면 해당 그룹의 블록 개수와, 무지개 블록의 개수를 반환한다
pair<int, int> Group_check(pair<int, int> here, int color, vector<vector<int>>& visited, vector<vector<int>>& this_group_visited)
{
	//일반 블록일때
	if (board[here.first][here.second] >= 1)
		visited[here.first][here.second] = 1;

	this_group_visited[here.first][here.second] = 1;

	pair<int, int> ret; //(블록 수, 무지개 블록 수)

	int block_ret = 1;
	int rainbow_ret = 0;

	//현재 위치가 무지개 블록일때
	if (board[here.first][here.second] == 0)
		rainbow_ret++;

	ret = make_pair(block_ret, rainbow_ret);

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && this_group_visited[there.first][there.second] == 0 && (board[there.first][there.second] == 0 || board[there.first][there.second] == color))
		{
			pair<int, int> group_check = Group_check(there, color, visited, this_group_visited);
			ret.first += group_check.first;
			ret.second += group_check.second;
		}
	}

	return ret;
}

//크기가 가장 큰 블록 그룹이 있는지 찾는다
bool Find_big()
{
	vector<vector<int>> visited(20, vector<int>(20, 0));
	int big_block_size = 0;
	int big_rainbow_size = 0;
	pair<int, int> big_point = make_pair(-1, -1);

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			//방문하지 않은 일반블록일때
			if (visited[i][j] == 0 && board[i][j] >= 1)
			{
				vector<vector<int>> this_group_visited(20, vector<int>(20, 0));
				pair<int, int> here = make_pair(i, j);
				pair<int, int> this_group_check = Group_check(here, board[i][j], visited, this_group_visited);
				int this_block_size = this_group_check.first;
				int this_rainbow_size = this_group_check.second;

				//더 큰 블록 그룹을 찾았을때
				if (big_block_size < this_block_size)
				{
					big_block_size = this_block_size;
					big_rainbow_size = this_rainbow_size;
					big_point = here;
				}

				else if (big_block_size == this_block_size)
				{
					//무지개 블록의 수가 더 클때
					if (big_rainbow_size < this_rainbow_size)
					{
						big_block_size = this_block_size;
						big_rainbow_size = this_rainbow_size;
						big_point = here;
					}

					else if (big_rainbow_size == this_rainbow_size)
					{
						big_block_size = this_block_size;
						big_rainbow_size = this_rainbow_size;
						big_point = here;
					}
				}
			}
		}

	//블록 그룹의 개수가 2개 미만일때
	if (big_block_size < 2)
		return false;

	vector<vector<int>> erased(20, vector<int>(20, 0));

	Erase(big_point, board[big_point.first][big_point.second], erased);
	result += (long long)(big_block_size * big_block_size); //점수 획득

	return true;
}

void Gravity()
{
	for (int j = 0; j < n; j++)
	{
		for (int i = n - 1; i >= 0; i--)
		{
			int this_block = board[i][j];

			//일반 블록일때
			if (this_block >= 0)
			{
				pair<int, int> here = make_pair(i, j);
				while (1)
				{
					pair<int, int> there = make_pair(here.first + 1, here.second);

					//더이상 내려갈 수 없을때
					if (there.first == n || board[there.first][there.second] != -2)
					{
						board[here.first][here.second] = this_block; //현재 자리에 블록 놓고 종료
						break;
					}

					//현재 자리는 빈칸으로 바꿈
					board[here.first][here.second] = -2;

					here = there;
				}
			}
		}
	}
}

void Turn()
{
	int temp_board[20][20];

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			temp_board[i][j] = board[j][n - 1 - i];
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			board[i][j] = temp_board[i][j];
		}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}

	while (1)
	{
		int group_check = Find_big();

		if (group_check == false)
			break;

		//중력 작용
		Gravity();

		//90도 반시계 방향 회전
		Turn();

		//중력 작용
		Gravity();
	}

	cout << result;

	return 0;
}