🧚‍♂️알고리즘🧚‍♂️ - 동적 계획법(DP) 5

골드 4

1915번: 가장 큰 정사각형

가장 큰 정사각형의 넓이 == 가장 큰 정사각형의 한 변의 길이를 구하는 문제로 생각해볼 수 있음!!

 

점화식 생각하기 :

D[i][j] : i j 위치를 꼭짓점으로 하는 정사각형 중에 최대 정사각형

해당 자리 위 왼쪽 완쪽 대각선 값이 모두 1 이상일 경우 더 작은! 값 + 1 하기 큰값은 정사각형이 아님

 

제일 큰 값을 제곱한 값이 정답이 됨

from sys import stdin

N,M = map(int, stdin.readline().split())
D = [[0 for _ in range(1001)]for _ in range(1001)]
maxresult = 0

for i in range(N):
    dlist = list(stdin.readline())

    for j in range(M):
        D[i][j] = int(dlist[j])
        # 점화식
        if D[i][j] == 1 and i>0 and j > 0:
            D[i][j] = min(D[i-1][j],D[i][j-1],D[i-1][j-1]) + 1 # 왼쪽 위쪽 대각선 왼쪽 중 작은 값 + 1
        
        # 최댓값 갱신 
        maxresult = max(maxresult, D[i][j] )

print(maxresult* maxresult)