[백준] 1915 가장 큰 정사각형 DP / python 골4

https://xn--acmicpc-lw16a.net/problem/1915

 

DP를 이용

 

뭔가 BFS같이 생겼는데, 아니었다

 

처음에는 정사각형을 판별하려면 2차원 배열을 돌아가면서 뭘 봐야 할까...하다가

현재 원소의 아래한칸 원소와 오른쪽한칸 원소를 보면 정사각형 여부를 알 수 있을까? 하면서 탐색했다

하지만 정사각형을 판별하는 방법이 되지는 못했고...

 

알고보니 현재 원소의 위쪽 한칸 원소와 왼쪽 한칸 원소, 대각선 왼쪽 위 원소를 봐야했다

 

 

현재 원소가 0이 아니라면

왼쪽, 대각선 왼쪽 위, 위쪽 원소 3개를 보고,

세 값의 min 값을 현재 원소에 더해준다

 

일단 정사각형이 형성 가능하려면,

현재 원소의 왼쪽, 왼쪽 위, 위쪽으로 같은 값만큼 확장이 되어야 하기 때문에

최대값을 고려하면, 그게 정사각형이 아니라 분리된 사각형이거나 직사각형이 될 수 있다

 

그래서 위 그림에서도 알 수 있다시피

왼, 왼위, 위 원소 세 값이 2인 경우에는, 각 지점에서 모두 변 2만큼 확장할 수 있다는 뜻이고

결국 변 길이가 3인 정사각형을 만들 수 있다

 

최대 정사각형은 업데이트 해준 dp 배열의 max값의 제곱이기 때문에

max값을 기록하는 변수를 두고 dp 업데이트마다 max 비교를 해줬다

 

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

arr = [list(map(int,input().strip())) for _ in range(n)]
dp = [ [0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        dp[i+1][j+1] = arr[i][j]
ma=0

for i in range(1,n+1):
    for j in range(1,m+1):
        if dp[i][j]!=0:
            dp[i][j]+=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])
            ma = max(ma,dp[i][j])

print(ma*ma)