[알고리즘] 프로그래머스 Lv2 가장 큰 정사각형 찾기

문제

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

풀이과정

처음 풀이:
반복문으로 하나하나 보면서 값이 1인 블럭에서 오른쪽으로 한칸씩 가면서 최대 길이 구하고 아래도 한칸씩 가면서 최대 길이를 구한 뒤 그 둘의 최솟값을 구한다.
그 최솟값만큼이 정사각형인지 확인한다.

이런 방식으로 함수를 두 개 짜서 반복문에 넣었더니 1개의 테스트 케이스에서 실패가 나왔고 효율성 테스트에서 모두 시간초과가 떴다.

해법은 DP였다!!

코드

def solution(board):
    n_row = len(board)
    n_col = len(board[0])
    MAX = 1

    dp = [[0] * (n_col + 1) for _ in range(n_row + 1)]
    if sum([sum(line) for line in board]) == 0:
        return 0
    if n_row == n_col and sum([sum(line) for line in board]) == n_col**2:
        return n_col**2

    for r in range(1, n_row+1):
        for c in range(1, n_col+1):
            if board[r-1][c-1] == 1:
                dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
                MAX = max(dp[r][c], MAX)
    return MAX ** 2

꼭 알고 가자

0, 1로 이루어진 2차원 배열에서
최대 크기 직사각형을 알고 싶으면 해당 블럭의 값이 1일 때, min(왼쪽, 위쪽) + 1 한 값을 해당 블럭에 담는 방식을 DP를 하고
최대 크기 정사각형을 알고 싶으면 해당 블럭의 값이 1일 때, min(좌상대각선, 왼쪽, 위쪽) + 1 값을 해당 블럭에 담는 방식으로 DP 코드를 작성해야 한다.