문제 링크

풀이 과정

• 주어진 표의 행과 열의 최대 길이는 각각 1,000입니다.
• 따라서, 처음에는 이중 for문을 사용하여, 각 위치에서 생성할 수 있는 정사각형 영역의 넓이를 구하고자 하였습니다.
  • 하지만, 표의 각 위치에서 생성할 수 있는 정사각형 영역의 넓이 및 탐험 종료 지점을 명확하게 알 수 없습니다.
    • 구현 복잡도가 높아질 있습니다.
    • 또한, 각 위치에서 정사각형을 매번 찾아야하므로, 시간 초과가 발생할 수 있습니다.
• 다른 방식으로 문제를 접근해봅시다.
• 최대 정사각형 넓이를 구하기 위해, 작은 정사각형들을 조합하여 더 큰 정사각형을 만드는(확장) 시각으로 바라봅시다!
  • DP를 사용하여, 앞선 결과를 누적하는 방법을 생각해볼 수 있겠지요!
• DP를 통해 문제는 다음과 같이 접근해봤습니다 :)
  • 이중 for문을 통해, dp[i][j] 값을 갱신
  • dp[i][j] = i행 j열에서 생성할 수 있는 정사각형 한 변의 최대 길이
  • 점화식 → dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
    • dp 값 중 0을 만나면, 더 이상 정사각형의 영역을 확장시킬 수 없습니다 (board 값이 0인 곳이 dp 값도 0이므로).
    • 이를 고려하기 위하여, min 연산을 수행한 것입니다.
• 마지막으로, DP 배열을 순회하여 가장 큰 값(정사각형 한 변의 최대 길이)을 찾은 후, 제곱을 취한 값이 정답이 됩니다!

전체 코드

def solution(board):
    rows, cols = len(board), len(board[0])
    dp = [[board[i][j] for j in range(cols)] for i in range(rows)]
    
    for i in range(1, rows):
        for j in range(1, cols):
            if board[i][j] != 0:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
    
    max_len = max(max(row) for row in dp)

    return max_len ** 2