Programmers - 가장 큰 정사각형 찾기

문제 링크

처음에 브루트포스로 풀었는데, 효율성테스트를 통과하지 못해서 계속 고민했다.
브루트 포스에서 필요 없는 경우를 가지치기 해가면서 케이스를 줄였는데도 통과하지 못했었는데
다른분이 작성한 풀이를 보고 DP로 구할 수 있다는 것을 이해했다.

d[i][j] 가 (i,j)가 우측 하단 끝점인 정사각형의 길이 일때, board[i][j]가 1이면(비어있지 않으면)
d[i][j]는 min(d[i-1][j],d[i][j-1], d[i-1][j-1])+1 이다

def solution(board):

    width = len(board[0])  # j
    height = len(board)  # i

    for i in range(1, height):
        for j in range(1, width):
            if board[i][j] == 0:
                continue
            board[i][j] = min(board[i-1][j], board[i][j-1], board[i-1][j-1])+1

    # print(board)

    max_length = 0
    for row in board:
        max_length = max(max_length, max(row))

    return max_length**2