[백준/C++]알고리즘 1051번 숫자 정사각형

안녕하세요.

알고리즘 1051번 숫자 정사각형문제를 풀어보도록 하겠습니다.

 

브루트포스의 전형적인 NM문제네여.

N,M이 50이하의 자연수이고 가장 큰 정사각형을 찾는 부분에서 min(N,M)이 반복되니까

대략 50*50*50번의 연산이 필요합니다. 이를 통해 완전탐색으로 풀 수 있다는 것을 알 수 있습니다!

그래서 저는 삼중 for문을 사용하여 구현을 해보았습니다.

​코드는 다음과 같아요.

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n = 0;
int m = 0;

int max_size = 1 ;

int main (void){
    cin>>n>>m;
    string arr[n];

    for (int i = 0 ; i < n ; i++){
            cin>>arr[i] ;
    }
    for (int i = 0 ; i < n -1; i++){
        for (int j = 0 ; j < m -1 ; j++){
            for(int k = 1 ; k < min(n,m) ; k++){
                if (i+k < n && j+k < m){
                char value = arr[i][j] ;
                if (arr[i][j+k] == value && arr[i+k][j] == value && arr[i+k][j+k] == value){
                    max_size = max(max_size,(k+1)*(k+1));
             
                }
                }
            }
        }
    }
    
    cout<<max_size<<endl;
   
        
}

 

긴 글읽어주셔서 감사합니다.