[백준/BOJ] 백준 2234번 : 성곽

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

2234번: 성곽

start지점이 속한 방의 넓이를 구하는 함수와, start위치가 속한 방과 인접한 방들 중 합쳤을 때 최댓값을 구하는 함수를 만들었다.

 

코드

#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <cstring>
using namespace std;

int n, m;
int board[50][50];
int discovered1[50][50];
int discovered2[50][50];
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int area_number = 100; //방을 100번 부터 번호를 매긴다
int area_size[2600];

int Solve1(pair<int, int> start)
{
	int this_size = 0;

	discovered1[start.first][start.second] = 1;

	queue<pair<int, int>> q;
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//넓이
		this_size++;

		for (int i = 0; i < 4; i++)
		{
			//해당 방향에 벽이 있을때
			if (board[here.first][here.second] & (1 << i))
				continue;

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

			if (there.first >= 0 && there.first < m && there.second >= 0 && there.second < n && discovered1[there.first][there.second] == 0)
			{
				discovered1[there.first][there.second] = 1;
				q.push(there);
			}

		}
		//같은 방들의 칸은 같은 숫자(100이상)로 채운다
		board[here.first][here.second] = area_number;
	}

	//해당 방의 크기를 저장해 놓는다
	area_size[area_number] = this_size;

	return this_size;
}

//start위치가 속한 방(영역)과 인접한 방들중 합쳤을때 최댓값을 구한다
int Solve2(pair<int, int> start)
{
	int sum_size = 0;

	discovered2[start.first][start.second] = 1;

	queue < pair<int, int>> q;
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

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

			if (there.first >= 0 && there.first < m && there.second >= 0 && there.second < n && discovered2[there.first][there.second] == 0)
			{
				//there가 다른 방일때
				if (board[there.first][there.second] != board[here.first][here.second])
				{
					sum_size = max(sum_size, area_size[board[there.first][there.second]] + area_size[board[here.first][here.second]]);
				}

				else
				{
					discovered2[there.first][there.second] = 1;
					q.push(there);
				}
			}
		}
	}

	return sum_size;
}

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

	memset(discovered1, 0, sizeof(discovered1));
	memset(discovered2, 0, sizeof(discovered2));

	int area_cnt = 0;
	int max_area1 = 0;
	int max_area2 = 0;
	int temp;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> temp;
			board[i][j] = temp;
		}

	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
		{
			//방을 발견했을때
			if (discovered1[i][j] == 0)
			{
				area_cnt++;

				max_area1 = max(max_area1, Solve1(make_pair(i, j)));

				area_number++;
			}
		}

	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
		{
			if (discovered2[i][j] == 0)
			{
				max_area2 = max(max_area2, Solve2(make_pair(i, j)));
			}
		}

	cout << area_cnt << "\n";
	cout << max_area1 << "\n";
	cout << max_area2 << "\n";

	return 0;
}