[프로그래머스 2레벨] 가장 큰 정사각형 찾기 (C++)

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

int solution(vector<vector<int>> board)
{
    int answer = 0;
    
    for(int i=1; i<board.size(); i++)
    {
        for(int j=1; j<board[0].size(); j++)
        {
            if(board[i][j] != 1) continue;
            board[i][j] = min({board[i-1][j-1], board[i-1][j], board[i][j-1]}) + 1;
            answer = max(answer, board[i][j]);
        }
    }

    return answer*answer;
}

 

현재 값을 기준으로 직전 3가지 값을 체크한다 (board[i-1][j-1], board[i-1][j], board[i][j-1])

해당 3가지 값들의 최소값을 기준으로 + 1한 값을 현재 위치에 저장해준다.

이는 모든 값이 1로 이루어진 정사각형 여부를 판별하는 것이다.

만약 하나라도 0인 값이 존재하면 0+1로 1을 그대로 유지하게 된다.

 

이를 누적하여 더하며 이어진 정사각형 크기를 판별하고, 이렇게 저장한 값은 한 변의 길이가 된다.

따라서 최종 출력은 제곱을 하여야한다.