[Programmers] P12905 가장 큰 정사각형 찾기

[Programmers] P12905 가장 큰 정사각형 찾기

Question

Language: Python

Difficulty: Gold 5

해당 좌표의 값이 1인 경우, 왼쪽, 위쪽, 왼쪽 대각선 위의 값을 비교해서, 해당 좌표를 끝점으로 하는 가장 큰 정사각형의 길이를 구할 수 있다.

위의 동작과정에 대한 예시를 보면 아래와 같이 board가 초기화되는 것을 확인할 수 있고, 최대 길이가 3인 정사각형이 존재함을 확인할 수 있다.

Solution

def solution(board):
    result=0
    n_rows=len(board)
    n_cols=len(board[0])
    for row in range(1,n_rows):
        for col in range(1,n_cols):
            if board[row][col]==0:
                continue
            board[row][col]=min(board[row-1][col],board[row][col-1],board[row-1][col-1])+1
            result=max(result,board[row][col])
    if n_rows==1 and n_cols==1 and board[0][0]==1:
        result=1
    return result**2