[DP] BOJ 1915 가장 큰 정사각형

문제

1915번: 가장 큰 정사각형

 

풀이

예제입력과 내가 자체적으로 만든 Test Case를 통해 풀이할 것이다.

예제입력

예제입력

예제입력은 위 사진의 표와 같이 입력된다.

 

1. dp 테이블을 만든다. 이때 기존에 주어진 n x m 보다 큰 (n+1) x (m+1) 크기의 테이블을 만든다. 테이블의 원소는 모두 0으로 초기화 한다. 아래 사진에는 설명을 위해 입력 테이블에 행과 열을 하나씩 추가했다.

dp 테이블과 입력 테이블을 동시에 표현

2. dp 테이블 기준으로 (1,1)부터 2x2 사각형의 오른쪽 아래 지점으로 가정한다. 그리고 한 칸씩 방문하여 입력 테이블에 1인 지점에서 점화식을 계산한다. 점화식은 오른쪽 아래를 제외한 모든 원소 중 최소값에 1을 더하여 현재 방문한 칸에 최신화한다. 이 점화식은 해당 칸을 사각형의 오른쪽 아래 지점에 위치했을 때 만들 수 있는 최대 사각형 크기의 제곱근이다.

3. 2번을 반복해서 dp 테이블을 완성 시킨다. dp 값중 최고값의 제곱이 가장 큰 사각형의 크기가 된다.

또 다른 예시

다음과 같은 입력이 있다고 생각하자. 최대 사각형의 크기는 9다.

1. dp 테이블을 만든다.

2. 입력예시의 2번 단계와 같이 dp 테이블을 점화식으로 채운다.

3. 테이블에서 가장 큰 값인 3의 제곱은 9 이므로 정답이다.

 

코드

위 두 문항처럼 2x2 사각형을 만드는 문제로 부터 kxk 사각형을 만드는 문제를 풀 수 있게됐다.

실버 단계의 dp와 골드 단계의 dp 문제 유형이 살짝 다르다. 하지만 근본적으로 같으므로 많은 유형을 풀며 단련해야겠다.

'''
이중for문을 써야한 다는 것
범위로 돌면서 찾아야 한다는 것 까지 생각했지만
점화식을 찾지 못했다.
'''

import sys

n,m = map(int,sys.stdin.readline().split())
arr = []

for _ in range(n):
    line  = sys.stdin.readline().rstrip()
    tmp = []
    for char in line:
        tmp.append(int(char))
    
    arr.append(tmp)

d = [[0] * (m+1) for _ in range(n+1)]
ans = 0

for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            d[i+1][j+1] = min(d[i+1][j], d[i][j+1], d[i][j]) + 1
            ans = max(ans, d[i+1][j+1])

print(ans * ans)