[프로그래머스 lv2] 가장 큰 정사각형 찾기

문제 보기

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

프로그래머스

 

참고 및 출처

설명 GOAT

너무 잘되어있어서 여기 보고 이해함

https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95-%EC%B0%BE%EA%B8%B0-%EB%8F%99%EC%A0%81-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-dp

[Python] 프로그래머스 level2 가장 큰 정사각형 찾기 (동적 프로그래밍, dp)

 

 

소스 코드

def solution(board):
    
    n,m = len(board), len(board[0])
    
    dp = [[0]*m for _ in range(n)]
    
    dp[0] = board[0]
    
    for i in range(1, n):
        dp[i][0] = board[i][0]
        
    for i in range(1, n):
        for j in range(1, m):
            if board[i][j] == 1:
                dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1
            
    answer = 0        
    for i in range(n):
        answer = max(answer, max(dp[i]))
            

    return answer**2