[🥇4 / 백준 1915 / 파이썬] 가장 큰 정사각형

 

1915번: 가장 큰 정사각형

 

문제

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

 

 

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.

입력

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

출력

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

 

예제 입력  4 4 0100 0111 1110 0010

예제 출력  4

 

풀이

 

다이나믹 프로그래밍의 누적 합을 이용하여 최대 크기의 정사각형을 찾는 문제이다.

 

필자는 정사각형이 아닌 직사각형으로 오해하고 알고 삽질을 조금 했는데, 여러분에겐 그런 불상사가 없길 바란다.

또한, 문제에서 말하는 정사각형은 속이 1로 전부 꽉 차있어야 한다. 즉, 테두리만 1이어서는 안 된다.

 

 

우선, 점화식은 다음과 같다.

 

if board[i-1][j] and board[i][j-1] and board[i-1][j-1]:
    board[i][j] = min(board[i-1][j],board[i][j-1],board[i-1][j-1])+1

 

현재 위치한 칸의 왼쪽, 위, 왼쪽 대각선 위가 모두 0이 아닐 경우, 그 중 가장 작은 것에 1을 더한 값이 현재 칸의 값이 된다.

dp를 완료하면, 아래의 왼쪽 배열은 오른쪽과 같이 바뀐다.

 

 

마지막으로, 배열에 있는 수 중 가장 큰 것을 제곱한 것이 문제의 답이 된다.

 

import sys
input = sys.stdin.readline

def solve():
    n,m = map(int,input().split())
    board = [list(map(int,list(input().rstrip()))) for _ in range(n)]
    for i in range(1,n):
        for j in range(1,m):
            if not board[i][j]:
                continue

            if board[i-1][j] and board[i][j-1] and board[i-1][j-1]:
                board[i][j] = min(board[i-1][j],board[i][j-1],board[i-1][j-1])+1

    print(max(map(max,[board[i] for i in range(n)])) ** 2)
    
solve()