[BOJ] 1915. 가장 큰 정사각형(DP).py.cpp

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

유형만 잘 파악하면 되는 문제라고 하는데..

DP는 다양한 문제를 많이 풀어보면서 

'아! 이런 유형에는 이렇게 풀어야 겠구나.' 라는 감을 기르는것이 중요하다고 한다.

쨋든.. 본론으로

입력이 아래 그림과 같을 때,

index out of range error를 피하기 위해 테두리는 0으로 채워주는 것이 좋다고 하였었다.

여기서 DP에 [i][j]까지의 가장 큰 정사각형의 한 변의 길이를 저장해주어야 한다.

(DP배열을 만들 때, index값이 의미하는 상태를 먼저 정의하는 것이 중요하다.)

먼저 결론부터 말하자면,

아래 그림과 같이 입력에서 가장 큰 정사각형을 찾는 조건은

(i, j)의 좌측, 대각선, 상단에 정사각형이 존재해야한다는 것이다.

(4,4)가 정사각형이 되기 위해서는 (4,3) (3,3) (3,4)가 정사각형이어야 한다는 것이다.

  

자, 여기서 또, 

그렇다면 점화식을 어떻게 세워야 하는가..! 가 문제다

DP에는 (i, j)까지의 가장 큰 정사각형의 한 변의 길이를 저장한다고 했다.

입력값 A에 따른 DP의 저장 상태를 보자.

               

가장 큰 정사각형의 한 변의 길이가 1이 될 수도 있다. 

(자기 자신이 가장 클 수도 있으니까)

그렇다면 한 변의 길이가 어떻게 저장되는지 살펴보자.

(i, j)까지 가장 큰 정사각형의 한 변의 길이는

A[i][j]가 1일 경우,

(i, j) 좌측, 대각선, 상단의 가장 큰 정사각형의 한 변의 길이의 최솟값에 + 1를 해주면 된다.

즉, 점화식을 써보면

DP[i][j] = min(DP[i][j-1], DP[i-1][j-1], DP[i-1][j]) + 1 이 된다.

Why(?)를 간단히 설명하자면, 

(i, j) 좌측, 대각선, 상단의 가장 큰 정사각형의 한 변의 길이 중 0이 있다면,

큰 정사각형이 만들어질 수 있는 조건((i, j)의 좌측, 대각선, 상단에 정사각형이 존재해야한다)을 만족하지 못한다.

또, 아래 그림과 같은 상황에서

i=4, j=4 일 때,

(i, j)까지 가장 큰 정사각형의 한 변의 길이를 구하기 위해서는 어떻게 점화식이 세워져야할지 생각해보자.

글로 동작을 설명하기란 쉽지 않은 것 같다.

마음처럼 표현이 잘 전달되는 것 같지 않은 느낌이고..

그래도 누군가 보았을 때, 혹은 나중에 내가 다시 봤을 때 한 번에 이해가 갔으면 좋겠다..

#. Python Code

N, M = map(int, input().split())
A = [[0 for i in range(M+1)] for j in range(N+1)]
DP = [[0 for i in range(M+1)] for j in range(N+1)]
 
for i in range(N):
    for idx, j in enumerate(list(map(int, list(input())))):
        A[i+1][idx+1] = j
 
for i in range(1, N+1):
    for j in range(1, M+1):
        if A[i][j]:
            DP[i][j] = min(DP[i-1][j], DP[i-1][j-1], DP[i][j-1]) + 1
 
print(max([max(i) for i in DP])**2)

line 11) A[i][j]가 1일 경우, 

(한 변의 길이가 1인 정사각형이므로 가장 큰 정사각형을 만드는데 필요한 조건이 된다.)

line 12) (i, j)까지 가장 큰 정사각형의 한 변의 길이를 구하기 위한 점화식

#. Cpp Code

#include <cstdio>
#include <algorithm>
using namespace std;
 
int A[1005][1005], DP[1005][1005];
 
int main(void)
{
    int n, m, i, j, mx = 0;
    //freopen("input.txt", "rt", stdin);
    scanf("%d %d", &n, &m);
    for (i = 1; i <= n; i++) 
        for (j = 1; j <= m; j++) 
            scanf("%1d", &A[i][j]);
 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (A[i][j] == 1) {
                DP[i][j] = min(min(DP[i][j - 1], DP[i - 1][j - 1]), DP[i - 1][j]) + 1;
                mx = max(mx, DP[i][j]);
            }
        }
    }
 
    printf("%d", mx * mx);
 
    return 0;
}

최적화가 필요하긴 하다..