[Baekjoon 1915] 가장 큰 정사각형

문제

💛Ⅳ [Baekjoon 1915 - 가장 큰 정사각형]

문제 풀이 방법

전형적인 다이나믹 프로그래밍 문제이다. 배열을 앞에서부터 순회하면서 각 자리에서 만들 수 있는 가장 큰 정사각형의 개수를 누적하여 더해간다.

1. 1이 하나라도 있는 경우 정사각형의 넓이는 1이므로 answer = 1로 초기화한다.
2. 칸이 0이 아니고, [대각선, 위, 왼쪽]에 0이 없다면 정사각형을 만들수 있으므로, [대각선, 위, 왼쪽]에서 가장 작은 값에 + 1한 값을 누적하여 저장한다.
3. 모든 칸이 0인 경우는 예외처리 해준다.

풀이 코드

Python

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
arr = [[int(x) for x in input().rstrip()] for _ in range(n)]

answer = 1
for i in range(1, n):
    for j in range(1, m):
        if arr[i][j] != 0 and 0 not in [arr[i-1][j-1], arr[i-1][j], arr[i][j-1]]:
            arr[i][j] = min(arr[i-1][j-1], arr[i-1][j], arr[i][j-1]) + 1
            answer = max(answer, arr[i][j])

if sum([sum(a) for a in arr]) == 0: # 모두 0일 때 예외 처리
    answer = 0
print(answer**2)