[Level 2] / [Python] 가장 큰 사각형 찾기 - DP (Dynamic Programming)

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

프로그래머스

---

해결 방법

DP (Dynamic Programming) 을 적용하여야 합니다.

알고리즘도 공부하였고 이해도 하였는데 막상 문제에 적용하려니 너무 어려웠습니다.

 

접근 방법

• 1행 (array[1][:])과 1열 (array[:][1])은 왼쪽, 위쪽이 없으므로 미리 처리합니다.

• 따라서 (1, 1)부터 탐색을 진행합니다.
• 진행하면서 현재 값이 1인지 확인 후 (왼쪽,위쪽,왼쪽+위쪽) 의 최솟값 + 1 을 현재 값으로 변환합니다.
• 배열이 끝날 때까지 반복 탐색을 합니다.

---

My Solution

def solution(board):
    answer = 0

    for r in range(1, len(board)):
        for c in range(1, len(board[0])):
            if board[r][c] == 0: continue            
            board[r][c] = min(board[r-1][c], board[r][c-1], board[r-1][c-1]) + 1
    
    for i in board:    
        if answer < max(i):
            answer = max(i)
        
    return answer * answer

print(solution([[1,1,1,1]])) # 1

print(solution([[0,1,1,1],
                [1,1,1,1],
                [1,1,1,1],
                [0,1,1,0]])) # 9

print(solution([[0,0,1,1],
                [1,1,1,1]])) # 4