가장 큰 정사각형 찾기

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

예를 들어

가장 큰 정사각형은

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

제한사항
표(board)는 2차원 배열로 주어집니다.
표(board)의 행(row)의 크기 : 1,000 이하의 자연수
표(board)의 열(column)의 크기 : 1,000 이하의 자연수
표(board)의 값은 1또는 0으로만 이루어져 있습니다.

입출력 예

 

문제해결과정

1. 처음에는 포문을 돌려서 각 행마다 1의 숫자를 세어 각각 넓이를 구했다.

2. 테스트케이스는 억지로 맞췄는데 제출하니 엄청 틀렸다.. 도저히 못풀어서 검색했는데 DP 라고 했다.

3. 아직까지는 문제에서 어떤 알고리즘을 사용해야 될지 감이 안잡히는데 연습을 많이 해봐야 알꺼같다..

---

def solution(board):
    n = len(board)
    m = len(board[0])
    answer = []
    
    for i in range(n):
        for j in range(m):
            if i > 0 and j > 0 and board[i][j] == 1:
                board[i][j] = min(board[i][j - 1], board[i - 1][j - 1], board[i - 1][j]) + 1
    
    for i in range(n):
        answer.append(max(board[i]))

    return max(answer) ** 2