[파이썬] [DP] 백준 1915 가장 큰 정사각형

문제 정의

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.
위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 

 

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

 

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

 

예제 입력 1

4 4
0100
0111
1110
0010

 

예제 출력 1

4

코드

n,m=map(int, input().split())

array=[list(map(int, list(input().rstrip()))) for _ in range(n)]

dp=[[0]*m for _ in range(n)]
result=0

for i in range(n):
    for j in range(m):
        if i==0 or j==0:
            dp[i][j]=array[i][j]
        elif array[i][j]==0:
            dp[i][j]=array[i][j]
        else:
            dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
        result=max(result,dp[i][j])    

print(result * result)

생각 정리