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 |
:
dp로 푼다.
(1,1)부터 시작해서 해당 값이 0이 아니면 (0이면 주변을 검사할 필요도 없이 정사각형이 만들어지지 않으므로) (i-1, j), (i, j-1), (i-1, j-1)을 검사해서 가장 작은 값+1을 저장한다.
즉, [a, b
c, d] 에서 보면 d를 검사 할건데 a,b,c 중 하나라도 0이 있으면 정사각형이 커봤자 면적이 1이다. 따라서 a,b,c 값의 최솟값+1을 d에 저장하면 된다.
결과적으로 전체 행렬에서 가장 큰 수를 찾아 제곱해주면 가장 큰 정사각형의 면적을 구할 수 있다.
dp 생각도 못했다..
def solution(board):
for i in range(1, len(board)):
for j in range(1, len(board[0])):
if board[i][j] != 0:
board[i][j] = min(board[i-1][j-1], board[i][j-1], board[i-1][j])+1
return max(map(max, board))**2