[Python][프로그래머스][Level2] 가장 큰 정사각형 찾기

[Python][프로그래머스][Level2] 가장 큰 정사각형 찾기

코드

def solution(board):
    for x in range(1,len(board)):
        for y in range(1,len(board[0])):
            if board[x][y]:
                board[x][y]=min(board[x-1][y],board[x-1][y-1],board[x][y-1])+1
    
    return max([max(i) for i in board])**2

dp로 풀었다.

board[x][y]가 1일 때, board[x-1][y],board[x-1][y-1],board[x][y-1]가 모두 1이어야 board[x][y] 에서 가장 큰 정사각형의 한변의 길이는 2가 된다.

마찬 가지로 board[x][y]가 1일 때, board[x-1][y],board[x-1][y-1],board[x][y-1]가 모두 2라면 가장 큰 정사각형의 한변의 길이는 3이 된다.

한개라도 0이거나 1이라면 다음 크기로 커질 수 없다.

이렇게 board의 위치별로 길이를 갱신해서

가장 긴 길이의 제곱이 답이 된다.