백준 1051 풀이

링크텍스트

이번에 푼 문제는 숫자 정사각형 문제이다.
처음 문제를 보고 어떻게 풀어야할지 조금 당황했다. 하지만 냉정하게 살펴보니 주어진 인풋의 최대값이 작아 브루트 포스로 풀 수 있겠다는 생각을 했다.

풀이 방법을 생각해내고 나면 이제 풀이는 간단하다.

주어진 배열에서 탐색을 해야하기 때문에 2중 for문과 가능한 정사각형의 한 변의 길이를 증가시키는 for문. 3중 for문으로 작성하면 된다.

먼저 정사각형이 이루어질 수 있는 한 변의 길이를 찾아야되는데 간단하다. n,m 둘 중 작은 것이 최대로 가능한 한 변의 길이이다.

그 다음 배열을 탐색하면서 현재 위치에서 찾는 사각형의 길이를 더한 값이 배열의 인덱스를 벗어나지는 않는지 검사하면서 길이를 더한 만큼의 배열의 위치에 있는 값고 현재 위치의 값을 비교해서 전부 일치하면 정사각형 아니면 답이 아니다.

여기서 크기가 1인 정사각형이 있을 수도 있기때문에 answer는 1부터 시작한다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main() {
	int answer = 0;
	int n;
	int m;
	cin >> n >> m;
	int arr[50][50];

	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;

		for (int j = 0; j < m; j++) {
			arr[i][j] = tmp[j] - '0';
		}
	}
	int maxWidth;
	if (n > m)
		maxWidth = m;
	else
		maxWidth = n;

	int x = 1;
	answer = 1;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 1; k < maxWidth; k++) {
				if (j + k < m && i + k < n) {
					if (arr[i][j] == arr[i][j + k] && arr[i][j] == arr[i + k][j] && arr[i][j] == arr[i + k][j + k]) {
						if (answer < k + 1) {
							answer = k + 1;
						}
					}
				}
			}
		}
	}

	cout << answer*answer << '\n';
}