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

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

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

 

코드

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

dp = [[0]*m for _ in range(n)]

arr = [list(map(int, input())) for _ in range(n)]

ans = 0

for i in range(0, n):
    for j in range(0, m):
        if arr[i][j] == 1:
            if i == 0 or j == 0:
                dp[i][j] = 1
            else:
                if arr[i-1][j] == 1 and arr[i-1][j-1] == 1 and arr[i][j-1] == 1:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                else:
                    dp[i][j] = 1
        ans = max(dp[i][j], ans)
        
print(ans**2)

 

풀이 과정

dp[i][j]는 해당 위치를 오른쪽 아래 꼭짓점으로 하는 정사각형의 한변의 길이를 나타내고자 함.

1. arr[i][j] 가 1일 때만 정사각형 크기를 계산

2-1. 1인 경우 위, 왼쪽, 왼쪽 대각선 위를 검사

2-2. 모두 1인 경우(정사각형인 경우) 해당 dp값(한변의 길이)의 최솟값 + 1을 한다.

3. 최종적으로 나온 dp배열의 최대값을 제곱하여 정사각형의 넓이를 계산