BAEKJOON 1051 - 숫자 정사각형

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

특별한 기법없이 완전탐색으로 풀 수 있었던 문제네요. 이미 구해놓은 최대값보다 큰 길이만 검사하는 가지치기 방법을 사용하면 시간 복잡도 문제 없이 풀 수 있는 문제인 것 같습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
      
#include <string>
using namespace std;
 
int height, width;
int map[51][51];
 
int getMaxLength()
{
    int ret = 0;
    for (int h = 0; h < height; h++)
    {
        for (int w = 0; w < width; w++)
        {
            int num = map[h][w];
            int maxLength = height - h - 1;
            if (width - w - 1 < maxLength)
                maxLength = width - w - 1;
            if (maxLength < ret)
                continue;
            for (int length = ret; length <= maxLength; length++)
            {
                if (map[h][w + length] == num && map[h + length][w + length] == num && map[h + length][w] == num)
                    ret = length;
            }
        }
    }
    return ret;
}
 
int main()
{
    cin >> height >> width;
 
    for (int h = 0; h < height; h++)
    {
        string str;
        cin >> str;
        for (int w = 0; w < width; w++)
            map[h][w] = str[w] - '0';
    }
    int ret = getMaxLength() + 1;
    cout << ret * ret << endl;
 
    return 0;
}