[완전탐색] 백준 1051 숫자 정사각형

www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

수행 시간: 1시간 (+- 10분)

나만 그런건지도 모르겠는데 브루트포스, 즉 완전탐색이나 그래프 같이 그래프 탐색 문제를 풀때, 알고리즘 아이디어 떠올리기가 가장 힘든거 같다. 이 문제는 실버3의 난이도 인데도 바로 직전 문제보다 안풀렸었던 것 같다. 이 문제의 아이디어는 정사각형의 변의 길이를 1~50 까지 하나씩 늘려가면서 점들을 찾아주는 방법을 사용하였다. 그러다보니 반복문이 3개나 들어가 있다. 

 

++ 내가 실수 했던 부분: 정사각형의 넓이는 1부터 시작하고 직사각형의 가로 또는 세로 길이보다 작아야된다. 

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int n, m;
int s[51][51];

int sol() {
	int e = min(n, m);
	int temp = 0;
	for (int i = 0;i < n;i++) {
		for (int j = 0; j < m;j++) {
			for (int square = 1; square < e;square++) {
				if (i + square < n && j + square < m) {
					if (s[i][j] == s[i + square][j] && s[i][j] == s[i][j + square] && s[i][j] == s[i + square][j + square]) {
						if (temp < square) {
							temp = square;
						}
					}
				}
			}
		}
	}
	int result = (temp+1) * (temp+1);
	return result;
}
int main() {
	cin >> n >> m;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			scanf_s("%1d", &s[i][j]);
		}
	}
	cout << sol();
}