이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 맨 처음에는 브루트포스를 통해 문제를 파악하였고, N, M의 범위가 1000까지기 때문에 당연히 시간 초과가 발생할 것이라 생각하였다. 그래서 다이나믹 프로그래밍으로 접근하였고, 다음과 같이 점화식을 구할 수 있었다.

정사각형을 만족하기 위해서는 현재 위치를 (i, j)라고 한다면 (i-1, j), (i-1, j-1), (i, j-1)의 위치를 모두 확인해보아야 한다. 이 중에서 가장 작은 숫자+1이 현재 (i, j)까지의 가장 큰 정사각형의 변이 된다. 이를 이용하여 점화식을 다음과 같이 정의하였다.

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

이 점화식은 grid[i][j]가 0일 경우에만 적용하여 지을 수 없는 땅을 피하도록 하였다.

Code

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