BOJ [1051] 숫자 정사각형

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

1. 분류

브루트 포스

2. 풀이

직사각형의 너비와 높이를 받아 내부의 정사각형 중 가장 큰 것을 구하는 문제이다.

네 모서리의 수가 같아야 정사각형으로 인정된다.

너비와 높이값이 최대 50이므로 O(n^4)이어도 풀 수가 있으므로 넉넉히 생각했다.

내부 정사각형을 하나하나 찾아가며 최대값을 뽑아내었다.

길이가 2인 정사각형부터 너비와 높이 중 작은 값(min)까지 검사했다.

내부에 for문이 2개 더 있는데 배열의 왼쪽 상단부터 우측 하단까지 일일이 방문하는 간단한 소스코드이다.

로직은 맞는데 계속 틀려서 곰곰히 생각을 해보니, 정사각형의 최소값을 0으로 주었기 때문이었다.

이런 실수는 특히나 조심해야겠다.

3. 소스코드

#include <cstdio>

int main()
{
	int n, m, min, a[51][51] = { 0 };
	scanf("%d %d", &n, &m);
	min = n > m ? m : n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%1d", &a[i][j]);

	int max = 1;

	for (int i = 1; i < min; i++)
	{
		for (int j = 0; j < n - i; j++)
		{
			for (int k = 0; k < m - i; k++)
			{
				if ((a[j][k] == a[j + i][k]) &&
					(a[j + i][k] == a[j][k + i]) &&
					(a[j][k + i] == a[j + i][k + i]))
				{
					max = max < (i + 1) ? (i + 1) : max;
					break;
				}
			}
		}
	}

	printf("%d\n", max * max);

	return 0;
}