주어진 배열에서 가장 큰 정사각형을 찾는 문제이다.
(0, 0) 지점에서 (n-1, m-1) 지점까지 순회하면서 dp를 활용하여 답을 찾았다.
각각의 칸 (r, c)에서는 자신을 둘러싸고 왼쪽+위쪽으로 2x2의 정사각형이 형성되는지 확인이 가능하다.
: (r, c), (r-1, c), (r, c-1), (r-1, c-1) 확인
dp[r][c]에는 어느 크기의 정사각형을 왼쪽+위쪽으로 이루고 있는지 저장한다.
이때 min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1])
을 구하면,
2x2내의 왼쪽+위쪽의 칸들이 최소로 이루고 있는 정사각형의 크기를 구할 수 있다.
dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
따라서 각각의 칸에 대해서 위의 코드를 적용시키면
정사각형의 크기를 누적해가면서 최대의 정사각형 크기를 구할 수 있다.
from sys import stdin
input = stdin.readline
n, m = map(int, input().split())
board = []
for _ in range(n):
board.append([int(x) for x in list(input().strip())])
dp = [[0]*(m+1) for _ in range(n+1)]
for r in range(1, n+1):
for c in range(1, m+1):
if board[r-1][c-1] == 1:
dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
max_width = max([max(row) for row in dp])
print(max_width**2)