문제

1과 0으로 이루어진 2차원 배열이 주어지는데 연속된 1로 만들 수 있는 가장 큰 정사각형의 넓이를 반환하는 문제이다.
DP 방식으로 풀면 되는 문제인데 DP는 역시 어렵다..

코드

def solution(board) -> int:
    mx = 0
    if len(board) == 1 or len(board[0]) == 1:
        return 1
    else:
        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][j-1], board[i-1][j], board[i-1][j-1])+1
                if board[i][j] > mx:
                    mx = board[i][j]
    return mx*mx

설명

맨 왼쪽 상단이 (0,0)이라는 가정하에 반복문이 (1,1)부터 시작된다. 각 (i,j)에서 왼쪽, 상단, 왼쪽 대각선 이 세 값 중에 min값을 구하고 그 값에 +1을 한 값을 (i,j)에 저장한다. 이 방식으로 반복문을 계속하면 2차원 배열에서 가장 큰 숫자가 가장 큰 정사각형의 한변의 길이가 된다. 그러므로 그 값의 제곱을 반환해주면 답이된다.

추가

테스트케이스에서 입력이 꼭 nn의 2차원 배열로 주어지지 않는다. 13이나 3*1로 입력이 될 수 있기 때문에 그 부분은 return 1로 처리해주었다.