문제 링크
풀이 과정
•
주어진 표의 행과 열의 최대 길이는 각각 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
Python
복사