[프로그래머스] Lv.2 가장 큰 정사각형 찾기 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12905
• 🔑 다이나믹 프로그래밍 (DP)
  • 점화식 : dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
  • board[i-1][j-1] == 1일 때 dp배열의 왼쪽, 위, 왼쪽 위 중 최솟값 + 1을 dp[i][j]에 기록한다.
  • board리스트(위) dp리스트(밑) 결과

 

def solution(board):

    answer = 0
    dp = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]
    
    for i in range(1, len(board) + 1):
        for j in range(1, len(board[0]) + 1):
            if board[i-1][j-1] == 1:
                dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
    
                if dp[i][j] > answer:
                    answer = dp[i][j]
                
    return answer ** 2