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

문제

접근 방법

각 정사각형의 꼭짓점만 확인해 주면 된다.
그렇기에 폭을 좁혀가며 각 정점에서의 4개의 꼭짓점을 확인해 주면 정사각형이 존재하는지 확인할 수 있는 것이다.

코드

#include <iostream>
#include <vector>
using namespace std;
int N, M, answer = 1;
vector<string> map;
void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    map = vector<string>(N);
    for (int y = 0; y < N; ++y)
    {
        cin >> map[y];
    }
}
bool isSquare(int width)
{
    for (int y = 0; y < N - width; ++y)
    {
        for (int x = 0; x < M - width; ++x)
        {
            if (map[y][x] == map[y][x + width] && map[y + width][x] == map[y + width][x + width] && map[y][x] == map[y + width][x]) // 꼭짓점이 같다면
            {
                return true;
            }
        }
    }
    return false;
}
void solve()
{
    for (int width = min(N, M); width >= 0; --width)
    {
        if (isSquare(width)) // 정사각형 있는지 확인
        {
            answer = width + 1;
            break;
        }
    }
    cout << answer * answer;
}
int main()
{
    input();
    solve();
    return 0;
}

풀이

가장 큰 정사각형 길이를 구하면 바로 나가도 된다.
그렇기에 가장 큰 길이부터 시작하여서 발견할 시 바로 반복문을 나와도 되는 것이다.

하지만 굳이 안 그러고 0부터 시작해도 N, M의 크기가 작기 때문에 시간문제는 없다.