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

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

1051번: 숫자 정사각형

풀이 :
- n*m 크기의 직사각형 안에서 꼭짓점의 수가 모두 같은 가장 큰 정사각형 찾기
- n의 최대 크기가 50이라서 각 칸 마다 다 돌아도 시간 초과가 나지 않는다
- 한 칸에 도착할 때마다 오른쪽으로 가면서 그 줄에 같은 수가 있는지,
   있다면 밑으로 가면서 같은 수가 있는지, 있다면 왼쪽으로 가면서 같은 수가 있는지
   이렇게 꼭짓점의 수를 탐색한다
- 전부 같다면 크기를 저장하면서 max값을 갱신한다
- 입력은 한 줄로 주어지기 때문에 string으로 받아서 다시 int형 배열로 바꿔줬다
 
코드 :

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

int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n, m, arr[55][55], ans = 0, cnt;
    string s;

    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> s; //string으로 받아서
        for(int j=1; j<=m; j++){ //int배열로 바꾸는데, 나중에 계산하기 편하도록
            arr[i+1][j] = s[j-1]-'0'; //1부터 시작
        }
    }
 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){ //이 칸은 왼쪽 위 꼭짓점
            cnt = 0; //매 칸마다 카운트는 초기화 
            for(int k=j+1; k<=m; k++){ // 오른쪽 위 꼭짓점을 찾을 때까지 
                cnt++; //cnt 카운트
                if(arr[i][j] == arr[i][k]){ //같은 수가 나오면 오른쪽 밑 꼭짓점을 찾을건데,
                    if(i+cnt <= n && (arr[i+cnt][k] == arr[i][j])){ //m과 n이 같다는 보장이 없기 때문에 앞 조건 필요
                        if(arr[i+cnt][j] == arr[i][j]){ //마지막 왼쪽 밑 꼭짓점까지 같다면
                            ans = max(ans, ((cnt+1)*(cnt+1))); //ans에 최댓값을 넣어준다
                        }
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}