[백준 1051] 숫자 정사각형 (C++)

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

문제

---

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

 

입력

---

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

 

출력

---

첫째 줄에 정답 정사각형의 크기를 출력한다.

 

문제 풀이

---

브루트포스 문제.

1*1 한 칸은  정사각형이므로 답은 적어도 1이상이다. 3중 반복문을 이용해 문제를 해결한다. 2 이상 N이하의 정사각형 크기를 정하고, 정사각형의 왼쪽 위 위치를 크기를 결정하는 반복문 안의 2중 for문으로 결정한다. 크기가 size일 때, 왼쪽 위 로 가능한 위치로는 행: 0 ~ (N - size), 열: 0 ~ (M - size) 까지 가능하다. 해당 위치가 정사각형의 왼쪽 위일 때, 나머지 3좌표의 위치를 구해 4좌표의 위치에 있는 숫자가 동일한지 확인한다. 동일하다면 현재 저장된 정사각형의 길이와 비교해 큰 값을 저장한다. 끝까지 탐색한 후 가장 큰 정사각형의 길이를 제곱해주면 된다.

 

아래는 코드.

 

#include <iostream>
#include <algorithm>
using namespace std;
int** arr;

bool isAllSame(int startX, int startY, int size)
{
	int leftUp = arr[startX][startY];
	int rightUp = arr[startX][startY + size - 1];
	int leftDown = arr[startX + size - 1][startY];
	int rightDown = arr[startX + size - 1][startY + size - 1];
	if (leftUp == rightUp && leftUp == leftDown && leftDown == rightDown)
	{
		return true;
	}
	else
	{
		return false;
	}
}

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

	int N, M;
	string str;
	cin >> N>>M;
	arr = new int*[N];
	int answer = 1;
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[M];
		cin >> str;
		for (int j = 0; j < M; j++)
		{
			arr[i][j] = str.at(j) - 48;
		}
	}
	for (int size = 2; size <= N; size++)
	{
		for (int i = 0; i <= N - size; i++)
		{
			for (int j = 0; j <= M - size; j++)
			{
				if (isAllSame(i, j, size))
				{
					answer = max(answer, size);
				}
			}
		}
	}
	cout << answer * answer << "\n";
	return 0;
}