문제 설명

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

예를 들어

1234

0111

1111

1111

0010

가 있다면 가장 큰 정사각형은

1234

0111

1111

1111

0010

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

def solution(board):
    answer = 0

    # 2차원 배열
    # 정사각형 -> index값 +
    h,w  = len(board), len(board[0])
    best = 0

    for i in range(h):
        for j in range(w):

            if board[i][j] == 1 :
                if i == 0 or j == 0 :
                    best = max(best, 1)
                else:
                    board[i][j] = min( # 하나라도 0이면 0
                        board[i-1][j-1] # 대각선 위
                        , board[i-1][j] # 상
                        , board[i][j-1] # 좌
                       )+1
                    best = max(best, board[i][j]) # 변의 길이

    return best*best

풀이

0 1 1 1

1 1 1 1

1 1 1 1

0 0 1 0 

이런 형태가 있다고 가정했을 때 

2행까지 체크하면

0 1 1 1

1 1 2 2

1 2 2 3

0 0 1 0 

이런 구조가 됨. 

즉, 좌상, 상, 좌 값을 체크하면서 그 값들에 값을 더해서 만듬.