이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 정사각형을 이루기 위해서는 최소한 현재 좌표에서 왼쪽, 왼쪽위대각선, 위쪽이 모두 1이 되어야 한다. 이러한 특징을 이용하여 dp리스트를 구성하였다. 2차원 리스트로 선언하고, 현재 좌표에 대한 dp는 왼쪽, 왼쪽위대각선, 위쪽에 대한 dp의 값 중 가장 작은값+1이 되도록 구현하였다. 점화식은 다음과 같다.

dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])+1

Code

n, m = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
dp = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
    dp[i][0] = int(grid[i][0])
for i in range(m):
    dp[0][i] = int(grid[0][i])
for i in range(1, n):
    for j in range(1, m):
        if grid[i][j] == '1':
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])+1
answer = 0
for i in range(n):
    answer = max(answer, max(dp[i]))
print(answer**2)