[백준-1051] 숫자 정사각형

문제

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

입력

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

출력

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

예제 입력 1 

3 5

42101

22100

22101

예제 출력 1 

9

---

<Code>

//1051] 숫자 정사각형 
#include <iostream>
#include <algorithm>
#define MAX 51
using namespace std;

int map[MAX][MAX];
int main() {
	freopen("input.txt","rt", stdin);
	
	int n, m, min;
	scanf("%d %d", &n, &m);
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			//%1d: 띄어쓰기없는 숫자를 하나씩 읽어야 함. 
			scanf("%1d", &map[i][j]);
		}
	}
	
	//정사각형 한변의 길이 범위 
	if(n<m) min=n;
	else min=m;
	
	while(min){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				//map범위를 벗어남. 
				if(i+min-1>n || j+min-1>m){
					break;
				}
				if(map[i][j]==map[i+min-1][j+min-1] &&
					map[i][j]==map[i][j+min-1] &&
					map[i][j]==map[i+min-1][j]){
						printf("%d", min*min);
						return 0;
				}
			}
		}
		min--;
	}
	
	return 0;
}

---

<Comment>

• 띄어쓰기 없이 들어오는 입력을 어떻게 1자리씩 받을지부터 약간의 띵킹이 필요했었음. 심지어 처음엔 왜 출력이 이상하게되는지 고민했었음.. -> scanf("%1d", &map[i][j]);  로 해결.
• 일단 정사각형의 넓이니까 아무리 커도 직사각형의 가장 작은 변이 정사각형 한변의 최댓값이 되겠구나, 그러면 그 범위를 먼저 저장해둬야 하는구나. 
• 이중 for문으로 배열을 돌면서 전체 배열의 범위를 벗어나는 경우를 먼저 if문으로 break해줬고,
• 그게 아니라면 하나를 기준 잡고 나머지 3개의 꼭짓점을 검사해서 모두 같을때만 min*min으로 넓이를 출력해줌.

---

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

1051번: 숫자 정사각형