백준 1915 가장 큰 정사각형(dynamic programming)

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

1915번: 가장 큰 정사각형

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1000 + 1;
int N, M;
int arr[MAX][MAX];
int dp[MAX][MAX];
int maxNum;

void biggestSquare()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (arr[i][j] == 1)
            {
                dp[i][j] = 1;
                if (dp[i - 1][j] >= 1 && dp[i][j - 1] >= 1 && dp[i - 1][j - 1] >= 1)
                {
                    dp[i][j] += min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]);
                    if (maxNum < dp[i][j])
                        maxNum = dp[i][j];
                }
            }
            if (maxNum < dp[i][j])
                maxNum = dp[i][j];
        }
    }

    cout << maxNum * maxNum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        string tmp;
        cin >> tmp;
        for (int j = 1; j <= M; j++)
        {

            arr[i][j] = tmp[j - 1] - '0';
        }
    }
    biggestSquare();
}

 

먼저, 오늘 블로그 방문자 수가 20명이나 된다....(어제는 0명이었는데) 괜히 뭔가 대단해진 것 같은 기분이다. 

 

일단, dp 문제이면서 이차원 배열이기 때문에

 

for(int i=1 ; i<=N ; i++){
	for(int j=1; j<=M ; j++){
    
    }
}

이 기본틀을 적었다. 물론 이렇게 기본틀을 잡는게 굉장히 비효율적일 수 있다.(이 틀로 해결 못하는 문제가 나올 수도 있는 것이기 때문에) 하지만, 초보자의 입장에서 기본틀이 있다는 것은 굉장히 도움이 된다. 기본틀을 바탕으로 for loop를 따라가다보면 금방 점화식을 발견할 수 있기 때문이다. 또한, 기본틀을 알고 있다는 사실만으로도 문제에 조금 더 냉정(?)하게 접근할 수 있게 된다.(이 모든 것은 내 경우에 한해서이다.)

 

일단 이 문제를 풀기 위한 기본적인 생각은 정사각형의 맨 우측, 맨 하단의 왼쪽(←), 위쪽(↑), 대각선으로 왼위쪽(↖)의 값이 반드시 1이상이어야 한다는 점이다. dp이기 때문에 가장 처음 만나게 되는 정사각형은 2x2의 모양이기 때문에 이 3 방향만 계속해서 확인해주면 된다. 

 

이 사실을 바탕으로 가장 처음으로 짠 점화식은

 dp[i][j] += max(max(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]);

였다. testcase가 이 점화식에서 별 탈 없이 제대로 된 값을 만들어주기 때문에 틀리지 않았다 생각했다. 하지만 testcase의 최대 정사각형은 2x2의 크기였기 때문에 문제를 일으키지 않은 것이었다.

 

만약 testcase가

0	1	0	0
1	1	1	1
0	1	1	1
0	1	1	1

이라 가정하자. 이 testcase를 저 점화식에 돌리게 되면

 

0	1	0	0
1	1	1	1
0	1	2	3
0	1	3	4

가 되어 버린다. 즉 3이 나와야 하는데 4가 나와 버리는 것이다. 이 때문에 max가 아닌 min을 사용해주어야 했다.

 

또, 중요했던 점은 바로 이 부분이었다.

 for (int i = 1; i <= N; i++)
    {
        string tmp;
        cin >> tmp;
        for (int j = 1; j <= M; j++)
        {

            arr[i][j] = tmp[j - 1] - '0';
        }
    }

 

i와 j의 시작을 굳이 1로 한 이유는 바깥쪽에 0을 둘러서 값을 구하기 쉽게 만들기 위함이었다.

하지만 이것 때문에 조금 혼동이 있었는데 나는 계속해서

arr[i][j] = tmp[j] - '0';

와 같이 작성해버렸다. tmp의 시작은 0임에도 불구하고 1부터 시작하게 만들어버렸던 것이다. 이거 찾느라 애좀 먹었다.