[백준 / C++] 1051번: 숫자 정사각형 (브루트포스 알고리즘)

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

1051번: 숫자 정사각형

 

난이도: solved.ac 실버 3

 

알고리즘 분류

구현, 브루트포스 알고리즘

 

접근 방법

모든 경우를 다 해보면 된다.

N과 M 중 더 작은 값을 Max_len이라고 하면, 한 변의 길이가 1인 정사각형부터 한 변의 길이가 Max_len인 정사각형까지 변의 길이를 1씩 증가시켜 가며 정사각형을 찾아주면 된다.

 

정사각형의 네 꼭지점의 합이 가장 큰 정사각형을 찾아야 하는데 나는 왼쪽 위 꼭짓점을 기준으로 사각형을 만들었다.

왼쪽 위 꼭짓점을 a, 왼쪽 아래 꼭짓점을 b, 오른쪽 위 꼭짓점을 c, 오른쪽 아래 꼭짓점을 d라고 하고, a = b = c = d이면 문제에서 구하라고 하는 조건을 만족하므로 해당 변의 길이(len)를 ans에 저장했다.

 

코드

#include <bits/stdc++.h>
 
using namespace std;
int N, M;
int arr[50][50];
string input;
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int i, j, ans;
	cin >> N >> M;
	for (i = 0; i < N; i++) {
		cin >> input;
		for (j = 0; j < M; j++)
			arr[i][j] = input[j] - '0';
	}
	int len, Max_len = min(N, M);
	int a, b, c, d;
	for (len = 1; len <= Max_len; len++) {
		for (i = 0; i <= N - len; i++) {
			for (j = 0; j <= M - len; j++) {
				a = arr[i][j];
				b = arr[i + len - 1][j];
				c = arr[i][j + len - 1];
				d = arr[i + len - 1][j + len - 1];
				if (a == b && b == c && c == d)
					ans = len;
			}
		}
	}
	cout << ans * ans;
}

 

성능

코드 제출 결과