[알고리즘 C++] 가장 큰 정사각형 찾기

https://programmers.co.kr/learn/courses/18/lessons/1879

오늘의 문제

가장 큰 정사각형 찾기

나의 풀이

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int solution(vector<vector<int>> board)
{
    int dp[board.size()][board[0].size()]; // dp
    int max = 0; // 최대값
    for(int i=0;i<board.size();i++)        // 첫 열 초기화
    {
        dp[i][0] = board[i][0];
        if(dp[i][0] > max)
            max = dp[i][0];
    }
    for(int i=0;i<board[0].size();i++)     // 첫 행 초기화
    {
        dp[0][i] = board[0][i];
        if(dp[i][0] > max)
            max = dp[i][0];
    }
    
    for(int i=1;i<board.size();i++)        // dp 프로세스
    {
        for(int j=1;j< board[0].size();j++)
        {
            if(board[i][j] == 1)
            {
               dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j], dp[i][j-1]))+1; // 최솟값 +1 저장
                if(dp[i][j] > max) // 최댓값 갱신
                    max = dp[i][j];
            }else
                dp[i][j] = 0; // 0인건 0
        }
    }
    return max*max; // 제곱
}

모범 답안

#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;
}

배울 점

• dp 초기화 방법 이렇게 하면 되는거였지!!!
• 행과 열을 따로 초기화 하지 말고 인덱스만 잘 고려해서 넣자
• row, col을 정의해서 사용하면 깔끔하다