[프로그래머스] 가장 큰 정사각형 찾기

문제

출처

입력

• 2차원 배열 board
  • 1 <= 행, 열 <= 1000
  • board의 원소 = 0 또는 1

출력

• 1로 이루어진 가장 큰 정사각형의 넓이

규칙

1. 정사각형은 축에 평행해야 함.
2. 1로 이루어진 정사각형은 내부까지 1로 차있어야 함.

접근

brute-force

단순하게 모든 경우를 다 찾아보자.
주어진 board가 m행 n열이라고 하자. 문제에서 요구하는 것은 가장 큰 정사각형이므로 가능한 최대 크기 min(m, n)부터 1까지 한 변의 길이를 줄여나가면서 1로 이루어진 정사각형을 찾아내면 된다.
다시 말해, 한 변의 길이가 length로 주어질 때 m행 n열의 각 원소를 좌측상단으로 하는 정사각형들 중 모든 원소가 1로 이루어져 있는 영역이 있다면 답은 length^2이 된다.

for length in range(min(m, n), 0, -1):
    for i in range(m):
        for j in range(n):
            if allOne(i, j, length):
                return length ** 2

그런데 이 경우 for문이 5개나 중첩되어 시간복잡도가 매우 높다. cumulative sum을 사용하여 allOne을 for문 한 개로 처리할 수도 있지만 m, n이 1000이므로 4중 for문 역시 시간초과를 피할 수 없다.

DP

이렇게 높은 시간복잡도를 가지는 문제는 수학적으로 답이 결정되거나, 기존 계산 결과를 재활용하는 문제인 경우가 많다. 이 문제의 경우 정사각형을 하나의 점과 변의 길이로 나타낼 수 있다는 점에 착안하여 결과를 재활용하는 방법을 찾을 수 있다.
board[i][j]의 값을 “(i, j)를 우측하단으로 하며, 1로 이루어진 정사각형 중 가장 큰 정사각형의 한 변의 길이”라고 정의하면, 다음과 같은 점화식을 얻을 수 있다.

# board[i][j]가 1인 경우
board[i][j] = min(board[i-1][j], board[i][j-1], board[i-1][j-1]) + 1

이해를 돕기 위해 예를 들어보자.
board[i-1][j] = 3, board[i][j-1] = 1, board[i-1][j-1] = 2이 주어졌다고 가정했을 때, 각각의 의미를 시각화하면 다음과 같다.

\[\begin{align} \text{board[i-1][j]} = \begin{matrix} ? & 1 & 1 & 1\\ ? & 1 & 1 & 1\\ ? & 1 & 1 & \color{red}1\\ ? & ? & ? & ?\\ \\ \end{matrix} \\ \text{board[i][j-1]} = \begin{matrix} ? & ? & ? & ?\\ ? & ? & ? & ?\\ ? & ? & ? & ?\\ ? & ? & \color{red}1 & ?\\ \\ \end{matrix} \\ \text{board[i-1][j-1]} = \begin{matrix} ? & ? & ? & ?\\ ? & 1 & 1 & ?\\ ? & 1 & \color{red}1 & ?\\ ? & ? & ? & ?\\ \end{matrix} \end{align}\]

즉, board는 어느 영역이 1로 차있는지에 대한 정보를 담고 있는 것이다. 이걸 모두 중첩시켜서 살펴보면 다음과 같다. (당연히 기존의 board[i][j]은 1이어야 한다.)

\[\begin{matrix} ? & 1 & 1 & 1\\ ? & 1 & 1 & 1\\ ? & 1 & \color{red}1 & \color{red}1\\ ? & ? & \color{red}1 & \color{red}1\\ \end{matrix}\]

따라서 board[i][j]의 새로운 값은 board[i-1][j], board[i][j-1], board[i-1][j-1] 중 가장 작은 값인 board[i][j-1]에 1을 더한 값이라는 걸 알 수 있다.

구현

for i in range(1, len(board)):
    for j in range(1, len(board[0])):
        if board[i][j]:
            board[i][j] = min([board[i-1][j], board[i][j-1], board[i-1][j-1]]) + 1
return max([max(li) for li in board]) ** 2