[1915] 가장 큰 정사각형 in python

https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

---

 

정사각형을 찾으려면

다이나믹 프로그래밍을 사용해야 한다.

 

 

** 정사각형 변의 길이를 구하는 방법 ** 

1. 해당 칸이 1로 채워져있어야 한다.

2. array[i-1][j], array[i][j-1], array[i-1][j-1] 중에서

가장 작은 값을 array[i][j]와 더해서 array[i][j]의 값을 갱신한다.

>> 정사각형이 되려면 현재 위치를 기준으로 한칸 위(i-1, j), 왼쪽으로 한칸 옆(i,j-1),

대각선 기준으로 왼쪽 위 (i-1, j-1)이 모두 0이 아닌 숫자로 채워져있어야한다. 

 

 

3. array[n][m]의 값 == 정사각형 변의 길이

 

 

n, m = map(int, input().split())
array = [list(map(int, input())) for _ in range(n)]
# 가장 큰 정사각형의 넓이
answer = 0

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

for row in array:
    answer = max(answer, max(row))
print(answer ** 2)