[BOJ][🟡4][백준#01915] 가장 큰 정사각형

문제 출처

BAEKJOON Online Judge #1915

문제

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

0 1 0 0

0 1 1 1

1 1 1 0

0 0 1 0

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

예제

입력

4 4
0100
0111
1110
0010

출력

4

My Sol

I, J = map(int, input().split())
mat = [list(map(int, input())) for _ in range(I)]

# 가로 연속 1
h_mat = [[0]*J for _ in range(I)]
for i in range(I):
    h_mat[i][0] = mat[i][0]
for i in range(I):
    for j in range(1, J):
        if not mat[i][j]: continue
        h_mat[i][j] = h_mat[i][j-1]+1

# 세로 연속 1
v_mat = [[0]*J for _ in range(I)]
for j in range(J):
    v_mat[0][j] = mat[0][j]
for i in range(1, I):
    for j in range(J):
        if not mat[i][j]: continue
        v_mat[i][j] = v_mat[i-1][j]+1

dp = [[0]*(J+1) for _ in range(I+1)]
for i in range(1, I+1):
    for j in range(1, J+1):
        if not mat[i-1][j-1]: continue
        l = dp[i-1][j-1]
        if not l:
            dp[i][j] = 1
            continue

        if v_mat[i-1][j-1] > l and h_mat[i-1][j-1] > l:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = min(v_mat[i-1][j-1], h_mat[i-1][j-1], l+1)

maxx = 0
for i in range(I+1):
    for j in range(J+1):
        if maxx < dp[i][j]:
            maxx = dp[i][j]
print(maxx**2)

DP를 이용하여 풀 수 있는 문제였다. 문제 풀이의 핵심은 어느 포인트에서 최대 크기의 길이를 가진다면, 그 다음 행과 그 다음 열이 계속 1이어야 오른쪽 대각선 아래에 1이 더 증가한 정사각형의 크기를 기록할 수 있다는 점이고, 만약 행과 열에서 중간에 잘린다면 잘린 포인트까지의 길이 중 가장 짧은 것이 새로운 가장 큰 정사각형의 변의 길이가 된다는 것이다.

1. 입력을 처리한다.
2. 행과 열에서 연속된 1을 체크하는 h_mat과 v_mat을 만들어준다.
3. 한 포인트의 최대 정사각형의 변의 길이를 저장하는 dp 2차원 배열을 만들고, 이를 위의 설명에 맞게 로직을 구성한다.
4. dp 2차원 배열에서 가장 큰 수를 확인한다. 이는 해당 포인트에서 가장 큰 정사각형의 변의 길이이므로 이를 제곱하여 출력한다.

결과

맞았습니다!!

모범답안

출처

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
arr = []

for i in range(n):
    now = list(map(int, input().rstrip()))
    arr.append(now)

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

answer = 0

for i in arr:
    answer = max(answer, max(i))

print(answer**2)

메모리와 연산시간이 절반정도 되는 풀이를 분석해보려 한다. 우선 stdin.readline을 이용해서 입력을 빠르게 받았다. 이 문제 같은 경우 ValueError가 발생해서 나는 제거해주었다. DP를 효율적으로 사용했는데, 한 포인트의 위쪽, 왼쪽, 왼쪽 위 대각선의 dp 값 중 최솟값에 1을 더한 값을 dp에 저장해주었다.