[Python] 백준 1915번: 가장 큰 정사각형

https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    n, m = map(int, input().split())
    nums = [[0]*(m+1)] + [[0] + [int(c) for c in str(input().rstrip())]
                          for _ in range(n)]

    dp = [[0]*(m+1) for _ in range(n+1)]
    max_length = 0

    for i in range(1, n+1):
        for j in range(1, m+1):
            if nums[i][j] == 1:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                max_length = max(max_length, dp[i][j])
            else:
                dp[i][j] = 0

    print(max_length**2)

 

DP[i][j]는 (i, j)에서의 가장 큰 정사각형이다. 예를 들어, 예시 입력 1에서 DP[2][2]는 2이다.

 

이것에 기반하여 특징을 잡아보자. 입력값이 아래와 같다고 해보자.

그럼 DP는 아래 사진처럼 된다.

그럼, 이것을 확장하면 아래처럼 된다.

왼쪽은 입력값, 오른쪽은 DP이다.

눈치를 챘을지 모르겠지만, DP의 값은 왼쪽, 위쪽, 왼쪽위 대각선의 것을 참조한다. 하지만, 단순히 3개의 값이 같을 때 그 값에서 1을 더하는 것이 아니다. 아래의 케이스를 보자.

이것들을 일반화하면, 다음과 같이 된다.

DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1

이것을 값이 1일 때와 0일 때를 구분하여 코드를 작성하면 된다. 물론 우리는 편의상 길이를 DP에 넣었기 때문에, (DP의 최댓값)^2를 출력하여야한다.