[Level2] 가장 큰 정사각형 찾기

🛠 문제

https://programmers.co.kr/learn/courses/30/lessons/12905

👩🏻‍💻 해결 방법

완전탐색으로 풀면 시간초과가 나기 때문에 dp를 사용해야했다
row, col이 0일 때를 제외하고 위, 왼쪽, 왼쪽 위를 확인하며 최솟값에 1을 더해주는 식으로 점화식을 세울 수 있다
정답을 구하기 위해 row마다 최댓값을 answer에 저장해준 뒤, 그 중에서 가장 큰 값을 제곱하여 넓이를 구할 수 있었다

소스 코드

def solution(board):
    row = len(board)
    col = len(board[0])
    
    for i in range(row):
        for j in range(col):
            if i == 0 or j == 0:
                continue
            if board[i][j] == 1:
                board[i][j] = min(board[i - 1][j - 1], board[i - 1][j], board[i][j - 1]) + 1
    
    answer = []
    for i in range(row):
        answer.append(max(board[i]))
    return max(answer)**2