1051. 숫자 정사각형

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

---

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

---

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

n, m = map(int, input().split())
rect = [input() for _ in range(n)]
size = 1

for i in range(n):
	for j in range(m):
		for k in range(j + 1, m):
			if (rect[i][j] == rect[i][k] and k-j < n - i):
				if (rect[i+(k-j)][k] == rect[i][j] and rect[i+(k-j)][j] == rect[i][j]):
					if (size < k - j + 1):
						size = k - j + 1
print(size**2)

입력 받은 모든 자연수를 탐색하며 결과를 찾아내는 브루트포스 알고리즘을 사용했다. 2차원 배열을 탐색하는 과정에서 반복문과 조건문이 생각보다 많이 중첩되어 신경이 쓰이긴 했지만 문제의 조건에서 N과 M의 범위가 크지 않고 문제를 푸는 것 자체가 복잡한 문제는 아니여서 우선 떠오르는 대로 빠르게 풀었다.

우선 첫번째 줄(i)의 첫번째 숫자(j)부터 해당 줄의 자신보다 큰 인덱스(k)에 같은 수가 있는지 확인하고, 있다면 그 거리만큼(k-j) 떨어진 줄의 같은 인덱스에 같은 숫자가 있는지 확인해서 조건이 충족하면 해당 정사각형의 변의 크기(k-j+1)를 구했다.

정사각형의 크기(size)의 초기값은 1로 두었고 size보다 큰 값이 구해질때마다 해당 변수의 값을 구해진 정사각형의 한 변의 크기로 리셋시켜주었다.

최종적으로 size의 제곱을 통해 정사각형의 크기를 출력시켜준다.