[백준] 1051번 숫자 정사각형 (C++)

https://www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

* 입력받은 숫자들 중에서 4개의 꼭짓점이 모두 같은 정사각형 중에서 최대크기를 구하면 되는 문제입니다. 완전탐색 + 구현 + 몇몇의 조건 주의

 

처음에 n과 m으로 행과 열의 크기를 알려줍니다. 이때 행열의 크기를 알 수 있고, 행열안에서 최대크기를 가지는 정사각형 또한 구할 수 있습니다.

이 부분에서 저는 실수를 하였는데요. 코드와 예시를 통해 알아보겠습니다.

for (int i = 1; i * i < n * m; i++)
     {
         start = i * i;
     }
start = sqrt(start); 

행렬의 전체크기보다 작은 제곱수를 구한후, 제곱근을 통해 길이를 구했습니다. 하지만 , 이렇게 최대 정사각형 크기를 구하면 다음과 같은 오류케이스로 인해 올바른 정사각형 최대 크기를 구하지 못합니다.

4 7 // 행크기 4 열크기 7 행열의 크기 28 가장큰 제곱수는 25 , 최대 정사각형 길이 5 하지만...

1234567
1234567
1234567
1234567

다음과 같은 경우에 저의 잘못된 풀이로는 최대 정사각형의 길이는 5이지만, 실제 행열에서 행은 4행 밖에 없으므로 5*5의 정사각형은 구할 수 없습니다. 

더 쉽게 !! 최대 정사각형 크기를 구할 수 있습니다. N과 M 즉 행열의 크기중 작은 값이 최대 정사각형의 크기가 됩니다.

7행1열의 크기라면 1*1의 정사각형이 1행7열의 크기라면 마찬가지로 1*1의 정사각형이 최대크기가 되어집니다.

    start = min(n,m); // 최대 정사각형 한변의 길이

전체 정답코드

int n, m;
string board[51];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {

        cin >> board[i];
    }

    int start;
    
    start = min(n,m); // 최대 정사각형 한변의 길이
    int answer = 0;
    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < m; k++)
        {
            for (int boxsize = 1; boxsize <= start; boxsize++)
            {
                if (i + boxsize - 1 > n || k + boxsize - 1 > m)
                    continue;
                if (board[i][k] == board[i][k + boxsize - 1] && board[i][k + boxsize - 1] == board[i + boxsize - 1][k + boxsize - 1] &&
                    board[i + boxsize - 1][k + boxsize - 1] == board[i + boxsize - 1][k] && board[i][k]==board[i+boxsize-1][k])
                {
                   answer = max(answer,boxsize);
                }
            }
        }
    }

    cout<<answer*answer;

    return 0;
}