가장 큰 정사각형 (python)

프로그래머스 문제 - 가장 큰 정사각형 LV2

효율성 때문에 개인적으로 레벨 2는 아닌것 같다고 생각...
https://programmers.co.kr/learn/courses/30/lessons/12905
DP문제

👀 깃헙 소스

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

입출력 예

board						answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]				4

솔루션
(1,1) 부터 네칸씩 memozation을 실행한다.
아래 오른쪽 칸이 1이면 나머지 세칸 중 최소값에 1을 더한 값으로 갱신한다.

# DP 적용 전 board 
[[0, 1, 1, 1],
 [1, 1, 1, 1], 
 [1, 1, 1, 1], 
 [0, 0, 1, 0]] 

# DP 적용 후 board
[[0, 1, 1, 1], 
 [1, 1, 2, 2], 
 [1, 2, 2, 3], 
 [0, 0, 1, 0]]

코드

# 파이썬
import itertools

def solution(board):
    M, N = len(board), len(board[0])
    for i in range(1, M):
        for j in range(1, N):
            if board[i][j] == 1:
                board[i][j] = min(board[i-1][j-1], board[i-1][j], board[i][j-1]) + 1
                print(board)

    return max(itertools.chain(*board))**2