[백준] 1915번 : 가장 큰 정사각형

문제 링크: www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

문제 유형: DP

 

백준 1915번 가장 큰 정사각형 문제

접근방식:

n x m 배열에서 1인 사각형을 구하는 문제이다. 정사각형 생성 가능 여부를 아는 방법은 대각선,왼쪽, 오른쪽에 최솟값의 + 1 을 해서 알 수 있다.

 

코드:

Python3

n,m = map(int,input().split())
matrix = [[0] * (m+1) for i in range(n+1)]

ans = 0
for i in range(1,n+1):
    c = input()
    for j in range(1,m+1):
        matrix[i][j] = int(c[j-1])
        if matrix[i][j] == 1:
            matrix[i][j] = min(matrix[i-1][j], min(matrix[i-1][j-1], matrix[i][j-1])) + 1
            ans = max(ans, matrix[i][j] * matrix[i][j])
print(ans)