[C++][프로그래머스] 가장 큰 정사각형 찾기

프로그래머스

 

📄 문제

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

 

📝 풀이

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

int solution(vector<vector<int>> board)
{
    int answer = 0;
    bool isZero = true;

    // 블록이 한줄만 되어있는경우?
    if(board.size() == 1 || board[0].size() == 1)
    {
        bool isEscape = true;
        
        for(int i = 0; i < board.size() && isEscape; ++i)
            for(int j = 0; j < board[0].size(); ++j)
                if(board[i][j] == 1)
                {
                    isEscape = false;
                    break;
                }
    
        // 0만 있는 경우 0을 리턴
        if(isEscape)
            return 0;
        // 1이 하나라도 있는경우, 1리턴
        else
            return 1;
    }
    
    // dp
    for(int i = 1; i < board.size(); ++i)
    {
        for(int j = 1; j < board[0].size(); ++j)
        {
            if(board[i][j])
            {
                board[i][j] = 1 + min({board[i-1][j-1],board[i-1][j],board[i][j-1]});
                answer = max(answer, board[i][j] * board[i][j]);
            }
        }
    }
    
    // [0][0], [1][0], [0][1]의 값도 함께 검사하여 리턴
    return max({answer, board[0][0], board[0][1], board[1][0]});
}

• dp를 이용하여 문제를 해결합니다.
• 2x2 영역을 차례대로 모두 검사하여 누적된 길이를 저장합니다.
• 2x2의 영역에 대한 최소값 + 1을 저장합니다. 낮은 값이 있다면, 그 값을 기준으로 정사각형이 이루어지기 때문입니다.
• board[i][j]가 1이 아니라면, 빈 공간이므로 계산하지 않습니다.