프로그래머스 - 가장 큰 정사각형 찾기

프로그래머스 - 가장 큰 정사각형 찾기

주어진 배열에서 각 행과 열에 대해서 최대 정사각형 크기를 미리 구해놓고, 가지치기를 하면서 (0, 0) ~ (N, M)까지 체크하는 방식으로 풀었다가 예외케이스를 만나서 DP방식으로 풀이를 바꿨다.

dp[i][j] = k가 의미하는 것은 (i, j)까지 최대 정사각형의 크기는 k라는 것이다.

dp식은 다음과 같다.
board[i][j]가 0인 경우는 dp[i][j]를 0으로 해주면 된다.
그 외의 경우에 대해서 dp[i][j]의 값은 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 중 가장 작은 값보다 1큰 값으로 해주면 된다.

코드는 아래와 같다.

#include <iostream>
#include <vector>

using namespace std;

#define TRIPLE_MIN(a, b, c) ((a > b) ? (b > c ? c : b) : (a > c ? c : a))

int solution(vector<vector<int>> board)
{
    int answer = 0;
    int row_size = board.size();
    int col_size = board[0].size();
    vector<vector<int>> dp(row_size, vector<int>(col_size, 0));
    for(int i=0;i<row_size;i++) {
        for(int j=0;j<col_size;j++) {
            if(!board[i][j])
                dp[i][j] = 0;
            else if(i - 1 < 0 || j - 1 < 0)
                dp[i][j] = 1;
            else 
                dp[i][j] = (!dp[i - 1][j] || !dp[i][j - 1] || !dp[i - 1][j - 1]) ? 
                    1 : TRIPLE_MIN(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;;
        }
    }
    for(int i=0;i<row_size;i++) 
        for(int j=0;j<col_size;j++) 
            answer = dp[i][j] > answer ? dp[i][j] : answer;
    answer *= answer;
    return answer;
}