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

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

1915번: 가장 큰 정사각형

문제 해결

가장 큰 정사각형의 크기를 구하는 것이기 때문에 DP를 이용하는 것이 좋다.

(i,j) 좌표를 끝으로 하는 가장 큰 정사각형은 (i-1,j-1) 좌표를 끝으로 하는 가장 큰 정사각형 크기에 영향을 받는다.

DP를 가장 큰 정사각형의 한 변의 길이라고 하면 DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) +1 이 될 것이다.

 

CODE

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[int(c) for c in str(input().rstrip())] for _ in range(n)]
dp = [[0 for _ in range(m)] for _ in range(n)]
length = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0: continue
        dp[i][j] = 1
        if i>=1 and j>=1:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
        length = max(length, dp[i][j])
print(length**2)