LV 2: 가장 큰 정사각형 찾기

문제 링크

LV 2: 가장 큰 정사각형 찾기

구현 방식

• 처음에 좌표를 한 칸씩 이동하면서 backtracking 방식으로 풀어보려 하였으나, row와 column의 크기가 1000이하인 관계로 TLE가 떴다

• dp를 이용해서 풀어주었다

  • row의 크기를 N, column의 크기를 M이라고 했을 때, board의 크기는 N*M이기 때문에 dp table의 크기를 (N+1)*(M+1)로 설정해주어야한다
    -> 그래야 board[N-1][M-1]위치까지 확인할 수 있음
  • N*M만큼 2중 for문을 순회하면서 board[i][j]가 1일 때 dp[i+1][j+1]의 값을 갱신해준다
    • 현재 위치에서, (상, 좌상, 좌)를 확인해주면 된다. (셋 중에서 가장 작은 값 + 1이 현재 위치의 값이 됨)
  • dp table의 최대값**2이 구하고자하는 정답이 된다

아직도 dp문제가 제일 어렵다..

코드

def solution(board):
    N = len(board); M = len(board[0])
    
    dp = [[0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if board[i][j] == 1:
                dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1 #현재 위치에서, (상, 좌상, 좌)를 확인해보면 됨
            
    max_width = 0
    for i in range(len(dp)):
        for j in range(len(dp[0])):
            max_width = max(max_width, dp[i][j])
    return max_width**2