백준 온라인 저지, 다이나믹프로그래밍 / 1915번: 가장큰정사각형 (파이썬 / 백준 골드문제)

문제

https://www.acmicpc.net/problem/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

접근 방법

- 값을 하나씩 탐색하며 탐색 중인 값의 왼쪽, 위, 왼쪽 대각선 위를 탐색하여 가장 작은 값을 저장해가며 최대값을 출력한다.

코드

# https://www.acmicpc.net/problem/1915
# 접근 방법
# 값을 하나씩 탐색하며 탐색 중인 값의 왼쪽, 위, 왼쪽 대각선 위를 탐색하여 가장 작은 값을 저장해가며 최대값을 출력한다.
import sys
n, m = map(int, sys.stdin.readline().split())
array = [[int(x) for x in sys.stdin.readline().rstrip()] for _ in range(n)]
result = 0
for i in range(n):
    for j in range(m):
        result = max(result, array[i][j])

for i in range(1, n):
    for j in range(1, m):
        if array[i][j] == 1:
            array[i][j] = min(array[i][j-1], array[i-1][j], array[i-1][j-1]) + 1
            result = max(result, array[i][j])
print(result ** 2)