[BF] 1051번 숫자 정사각형

1051번 숫자 정사각형

 

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

 

문제

N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

 

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

 

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

 

예제 입력

3 5
42101
22100
22101

 

예제 출력

9

 

해결방법

N 의 조건이 N ≤ 50 이고, 시간복잡도는 O(N^3) 이므로 모든 경우를 탐색한다

 

모든 노드에서 정사각형을 만들어 봐야한다. 이는 N^2 의 시간이 발생한다

또한 한노드에서 만들 수 있는 정사각형수는 최대 N개 이다

따라서 125,000 의 시간으로 무사히 탐색 가능하다

 

또한 4개의 수를 비교할 때 값을 한번에 비교하면 정상적인 비교가 되지 않는다

// 비교 X
if(map[x][y] == map[nx][y] == map[x][ny] == map[nx][ny])

// 비교 O
if(map[x][y] == map[nx][y] && map[x][y] == map[x][ny] && map[x][y] == map[nx][ny])

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <algorithm>
#define MAX 51
using namespace std;

int n,m,ans;
int map[MAX][MAX];

void solve(int x,int y){
    int i = 0;
    
    while(1){
        int nx = x + i;
        int ny = y + i;
        
        if(nx >= n || ny >= m) break;
        
        if(map[x][y] == map[nx][y] && map[x][y] == map[x][ny] && map[x][y] == map[nx][ny]){
            ans = max(ans, (i+1)*(i+1));
        }
        
        i++;
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL); cout.tie(NULL);
    
    scanf("%d %d",&n,&m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%1d",&map[i][j]);
        }
    }
    
    ans = 0;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            solve(i,j);
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}