[Python] 프로그래머스(Lv2) - 가장 큰 정사각형 찾기

안녕하세요 :)

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

아래 그림과 같이 0과 1로 이루어진 배열에서 가장 큰 정사각형을 찾는 문제입니다.

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.
  

제한사항에서 r과 c의 길이가 1000이하라 ,,, for문을 최대 두번인 O(n^2)으로 해결해야 하는 문제입니다.

어떻게 for문을 두번만 돌고 답을 구할 수 있을지 엄청 고민해봤는데 .... 결국 해답을 찾지 못해서 검색해봤네요 ㅠㅠ

솔루션은 (i, j) 위치의 값을 (i, j) 위치에서 만들 수 있는 가장 큰 정사각형 한 변의 길이가 되도록 만들어 주는 것입니다.

왼쪽 (i, j-1), 위쪽 (i-1, j), 대각선 위치 (i-1, j-1) 값 중에서 최소값에 + 1로 값을 갱신해줍니다.

def solution(board):
    answer = 0
    r = len(board)
    c = len(board[0])

    square = [[0] * (c+1) for _ in range(r+1)]

    for i in range(r):
        for j in range(c):
            square[i+1][j+1] = board[i][j]

    for i in range(1, r+1):
        for j in range(1, c+1):
            if square[i][j] != 0:
                square[i][j] = min(square[i-1][j], square[i][j-1], square[i-1][j-1]) + 1
                answer = max(answer, square[i][j])

    return answer * answer

참고한글:
[프로그래머스] - 가장 큰 정사각형 찾기