[백준] 1051번 숫자 정사각형 (Python)

풀이

주어진 2차원 배열에서 만들어 낼 수 있는 정사각형의 크기를 min(n, m) 을 통해 제한한다.
만들 수 있는 모든 제한된 정사각형의 꼭짓점을 비교하고 모두가 동일할 경우 정사각형의 넓이를 update 한다.
모든 반복이 끝나면 ans 를 출력한다.

주어진 예제를 보자.

예제에서 주어진 배열은 3x5 배열이다. 이때 만들 수 있는 가장 큰 정사각형은 3x3 의 크기를 가진다.

때문에 꼭지점 비교를 위한 반복문을 최대 3번, k 를 통해 반복할 수 있다.

k 가 반복될 때 마다 n, m 의 범위가 줄어들어야하기 때문에 반복되는 i, j 의 범위를 각각 n-k, m-k 로 제한해준다.

이후 조건문을 통해 모든 꼭짓점이 같을 경우 정사각형의 크기를 수정해줘야하는데 이는 (k+1)**2 을 통해 알 수 있다.

소스코드

import sys
 
input = sys.stdin.readline
 
n, m = map(int, input().split())
sq = [list(input().rstrip()) for _ in range(n)]
ans = 0
 
for k in range(min(n, m)):
    for i in range(n-k):
        for j in range(m-k):
            if sq[i][j] == sq[i][j+k] == sq[i+k][j] == sq[i+k][j+k]:
                ans = max(ans, (k+1)**2)
 
print(ans)

References

BOJ 1051 - 숫자 정사각형