2022.03.22 [백준] (python 파이썬) 가장 큰 정사각형

 

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

1915번: 가장 큰 정사각형

 

---

풀이

문제를 해결하기 위해 우선 arr배열에 문제에서 주어진 배열을 넣었다. 

그리고 dp배열을 (n+1)X(m+1)크기로 만들었다. 이유는 이전 값을 비교해야하기 때문이다.

만약 arr[i][j]가 0이면 정사각형을 만들 수 없으므로 넘어가고 1이면 dp[i+1][j],dp[i][j+1],dp[i][j]을 비교하여 가장 작은 값의 +1 값을 dp[i+1][j+1]에 넣어준다.

dp[i+1][j+1]에는 arr[i][j]를 정사각형의 우측하단 꼭짓점으로하여 만들수 있는 정사각형의 변의 길이를 저장합니다.

그리고 lens에는 최대 변의 길이를 저장할 수 있도록 if문을 이용했다.

n,m=map(int,input().split())
arr=[]
for _ in range(n):
    arr.append(list(map(int, input())))
 
dp=[[0 for _ in range(m+1)] for _ in range(n+1)]
lens=0
for i in range(n):
    for j in range(m):
        if arr[i][j]==1:
            dp[i+1][j+1]=min(dp[i+1][j],dp[i][j+1],dp[i][j])+1
 
            if dp[i+1][j+1]>lens:
                lens=dp[i+1][j+1]
print(lens**2)