코드 설명

n, m = map(int, input().split())
g = [list(map(int, input().strip())) for _ in range(n)]
dp = [[0] * m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if i >= 1 and j >= 1 and g[i][j]:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
        else:
            dp[i][j] = g[i][j]

size = max(sum(dp, []))
print(size ** 2)

DP는 사각형의 우측 하단을 기준으로 만들 수 있는 최대 크기의 정사각형의 크기를 저장한다.

최대 크기의 정사각형을 찾는 방법은 오른쪽, 위쪽, 오른쪽 위의 DP를 확인하고 (사각형의 확장 가능성) 그 중 가장 작은 DP 값에 +1을 하면 됨.

점화식은

시간복잡도는 배열 순회 $O(NM)$

gemini interactive ai로 시각화 함.