[C++] 가장 큰 정사각형 찾기 - DP

문제 유형

이 문제는 2차원 DP(동적 계획법) 유형이다.

각 칸에서 만들 수 있는 가장 큰 정사각형의 크기를 이전 칸들의 결과를 이용해 계산한다.

DP 상태

board[i][j]를 다음 의미로 사용한다.

(i, j)를 오른쪽 아래 꼭짓점으로 하는 가장 큰 정사각형의 한 변 길이

원래 값은 0 또는 1이지만, 계산하면서 DP 값으로 바꿔 저장한다.

점화식

현재 칸이 0이면 정사각형을 만들 수 없다.

board[i][j] = 0

현재 칸이 1이면:

board[i][j] =
min(위쪽, 왼쪽, 왼쪽 위 대각선) + 1

코드로는:

board[i][j] =
    min({board[i - 1][j],
         board[i][j - 1],
         board[i - 1][j - 1]}) + 1;

세 방향 중 하나라도 작으면 정사각형을 크게 확장할 수 없기 때문에 min을 사용한다.

예시

원래 표:

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

DP 계산 후:

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

가장 큰 값이 3이므로 가장 큰 정사각형의 넓이는:

3 × 3 = 9

정답 코드

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> board) {
    int row = board.size();
    int col = board[0].size();
    int maxSide = 0;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {

            if (board[i][j] == 1) {
                if (i > 0 && j > 0) {
                    board[i][j] =
                        min({board[i - 1][j],
                             board[i][j - 1],
                             board[i - 1][j - 1]}) + 1;
                }

                maxSide = max(maxSide, board[i][j]);
            }
        }
    }

    return maxSide * maxSide;
}

 

 

다른 풀이

#include<vector>
using namespace std;


int dp[1001][1001] = {0};

int solution(vector<vector<int>> board)
{
    int ans = 0;
    int row = board.size();
    int col = board[0].size();
    for (int i = 1; i <= row; ++i)
    {
        for (int j = 1; j <= col; ++j)
        {
            if(board[i-1][j-1] != 0 )
            {
                dp[i][j] = min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) + 1;
                ans = max(ans, dp[i][j]);
            }
        }
    }
    return ans*ans;
}