[BOJ/백준] 4095 최대 정사각형

import sys

def input():
    return sys.stdin.readline().rstrip()
while True:
    N,M = map(int,input().split())
    if not N+M:
        break
    dp = [[0 for _ in range(M+1)]]

    for _ in range(N):
        temp = [0]+list(map(int,input().split()))
        dp.append(temp)
    result = 0
    
    for x in range(1,N+1):
        for y in range(1,M+1):
            dp[x][y] = min(dp[x-1][y],dp[x][y-1],dp[x-1][y-1]) + 1 if dp[x][y] else 0

            if result<dp[x][y]:
                result = dp[x][y]
    print(result)

 

이 문제는 유명한 문제이다. 원래 행렬에서 최상단과 좌측에 0인 배열을 넣어주고, 탐색을 해주면 된다.

 

그리고 (x-1,y), (x,y-1), (x-1,y-1) 의 최소값에 + 1을 해준다. 만약 dp[x][y]에 1이 있을 경우에만

 

그렇지 않을때에는 0을 넣어주면 된다.

 

그리고 탐색을 하면서 최대값을 갱신해주면 된다.