[백준/알고리즘] 1051번 숫자 정사각형 (실버 3)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 1051번

 

N x M 크기의 직사각형의 각 칸에 한 자리 숫자가 적혀 있다. 직사각형 내에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾으시오.

 

풀이 알고리즘 : 완전탐색

 

정사각형의 최대 크기는 N과 M중 작은 값이다.

 

maxlen을 min(M, N)으로 초기화 한 후, 이중 for문을 통해, 왼쪽 위의 점의 좌표를 기준으로 정사각형이 되는지 탐색한다.

 

참고

 

소스코드 보기

 

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 1, 0};
int diry[4] = {0, 1, 1};

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m, maxlen;
	cin >> n >> m;
	maxlen = min(n, m);
	vector<string> arr;
	for(int i = 0; i < n; i++) {
		string s; cin >> s; arr.push_back(s);
	}
	for(int size = maxlen; 0 < size; size--) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				bool issquare = true;
				for(int k = 0; k < 3; k++) {
					int y = i + diry[k] * (size - 1);
					int x = j + dirx[k] * (size - 1);
					if(0 <= x && x < m && 0 <= y && y < n) {
						if(arr[y][x] == arr[i][j]) {
							issquare = issquare && true;
						} else {
							issquare = false;
						}
					} else {
						issquare = false;
					}
				}
				if(issquare) {
					cout << size * size;
					return 0;
				}
			}
		}
	}

	return 0;
}