[프로그래머스/파이썬] Level 2 가장 큰 정사각형 찾기

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

---

알고리즘 분류

• 다이나믹프로그래밍

문제풀이

처음 떠올린 방법은 board를 돌면서 정사각형 크기를 1부터 1000까지 늘려나가며 탐색하는 완전탐색이었으나, O(n^3)의 시간복잡도가 걸리므로 정답이 아니다.

board에서 하나의 좌표를 확인할 때마다 그 이전의 결과값에 따라 값이 정해지므로 해당 문제의 유형은 다이나믹프로그래밍이다.

예를 들어,
[[0, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1],
[0, 0, 1, 0]] 에서
(1,1)부터 각각의 좌표에서 왼쪽, 위, 왼쪽위대각선 이 3개의 값을 확인해서 최소값+1을 갱신해나간다.

[[0, 1, 1, 1],
[1, 1, 2, 2],
[1, 2, 2, 3],
[0, 0, 1, 0]]

소스코드

def solution(board):
    m,n=len(board),len(board[0])

    for i in range(1,m):
        for j in range(1,n):
            if board[i][j]==1:
                board[i][j]=min(board[i-1][j-1], board[i][j-1], board[i-1][j])+1
    
    result=0
    for i in board:
        for j in i:
            if j>=result:
                result=j
    
    return result**2