가장 큰 정사각형 찾기
문제 설명
1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
시각화
위와 같을 때 가장 큰 정사각형은 초록색 영역과 같다.
문제 해결 과정
3 X 3 정사각형을 어떠한 것으로 볼 수 있냐면
파랑색 영역의 4개의 조합이라고 볼 수 있다. 1, 2, 3, 4 가 적혀있는 부분에서 왼쪽, 위쪽, 왼쪽 대각선 부분이 1 X 1 사각형이라면 2의 정사각형이라고 볼 수 있다. 마찬가지로 4의 위치에서 1, 2, 3 이 2 X 2 의 정사각형이라면 4는 3 X 3 정사각형이라고 볼 수 있다.
즉 현재 위치에서 board[y][x - 1], board[y + 1][x], board[y - 1][x - 1] 최솟값에 + 1 을 하면 된다.
전체 코드
board 를 for 으로 돌면서 1인 경우에 가장 큰 정사각형 사이즈를 구하면 된다. 현재 위치에서 가장 큰 값을 구하기 때문에 DP 로 풀 수 있다.
def solution(board):
rows = len(board)
cols = len(board[0])
dp = [[0] * cols for _ in range(rows)]
max_side = 0
for i in range(rows):
for j in range(cols):
if board[i][j] == 1:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
max_side = max(max_side, dp[i][j])
return max_side ** 2
