[레벨 2] 가장 큰 정사각형 찾기

int solution(vector<vector<int>> board)
{
    int answer;
    int boardY = board.size();
    int boardX = board[0].size();
    int y, x;
    int result = 0, maxResult = 0;
    for (y = 0; y < boardY; ++y)
    {
        result = 0;
        for (x = 0; x < boardX; ++x)
        {
            if (y + 1 >= boardY || x + 1 >= boardX)
                continue;
            if (board[y][x] == 0)
                continue;
            else if (board[y + 1][x + 1] == 0)
                continue;
            else
            {
                int sqaureLength = 1;
                bool notSqaure = false;
                while (true)
                {
                    if (y + sqaureLength >= boardY || x + sqaureLength >= boardX)
                        break;
                    if (board[y + sqaureLength][x + sqaureLength] == 0)
                        break;
                    ++sqaureLength;
                }
                for (int i = y; i < y + sqaureLength; ++i)
                {
                    if (notSqaure)
                        break;
                    for (int j = x; j < x + sqaureLength; ++j)
                    {
                        if (board[i][j] == 0)
                        {
                            notSqaure = true;
                            break;
                        }
                    }
                }

                if (!notSqaure)
                {
                    result = sqaureLength * sqaureLength;
                    if (result > maxResult)
                        maxResult = result;
                }
            }
        }
    }

    return answer = maxResult;
}

일단 떠오른 해결법으로 푼 코드.

현재 인덱스의 요소가 1이고 대각선(오른쪽아래) 요소가 1인지 체크. 

조건이 통과되었다면 정사각형이 되는지 체크.

크기 결과 저장. (maxResult 비교)

 

채점결과 테스트케이스 1,6,17실패 효율성 3개 시간초과.

 

다른사람의 풀이를 확인

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

int solution(vector<vector<int>> board)
{
    int answer = board[0][0];
    int boardY = board.size();
    int boardX = board[0].size();
    int y, x;
    for (y = 1; y < boardY; ++y)
    {
        for (x = 1; x < boardX; ++x)
        {
            if (board[y][x] >= 1)
            {
                board[y][x] = 1 + min({ board[y - 1][x - 1],board[y - 1][x],board[y][x - 1] });
                answer = max(answer, board[y][x]);
            }
        }
    }
    return answer * answer;
}

이 풀이는 현재 요소의 기준으로 왼쪽상단,위,왼쪽을 체크하여 2x2 정사각형이 만들어지는지 체크.

 

핵심코드는 이것

if (board[y][x] >= 1)
{
    board[y][x] = 1 + min({ board[y - 1][x - 1],board[y - 1][x],board[y][x - 1] });
    answer = max(answer, board[y][x]);
}

board의 요소가 1이라면 왼쪽상단,위,왼쪽의 요소를 min함수를 통해서 체크. (모두 1이라면 1이나오고 아니라면 0)

0이나온다면 board의 요소엔 다시 1이 저장이 되며 정사각형이 만들어지면 2가 만들어진다.

이것을 예로들면

정사각형이 만들어지는 라인을 따라 계산을 하다보면

왼쪽상단, 위, 왼쪽의 기준으로 1인 자리의 요소가 2가 되며. 그 값은 누적이 된다.