[BOJ #1051] 숫자 정사각형

BOJ #1051, 숫자 정사각형 문제입니다.

 

입력 범위를 general하게 바라보면 계산량이 좀 많습니다만 입력 범위가 매우 작아서(N, M <= 50) 시간 초과가 나지 않습니다. 간단하게 브루트포스로 해결할 수 있습니다.

 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void getMatrixInput(int** matrix, int N, int M) {
	int offset = '0' - 0;
	char* inputTemp = (char*)malloc(sizeof(char) * (M + 1));

	for (int i = 0; i < N; i++) {
		scanf("%s", inputTemp);
		for (int j = 0; j < M; j++)
			matrix[i][j] = inputTemp[j] - offset;
	}

	free(inputTemp);
}

int isItSquare(int** matrix, int i, int j, int side) {
	int val = matrix[i][j];
	if (val == matrix[i][j + side - 1] && val == matrix[i + side - 1][j] && val == matrix[i + side - 1][j + side - 1])
		return 1;
	return 0;
}

int solve(int** matrix, int N, int M) {
	int max = (N > M) ? N : M;
	for (int side = max; side >= 2; side--) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!(i + side - 1 < N && j + side - 1 < M))
					continue;
				else {
					if (isItSquare(matrix, i, j, side))
						return side;
				}
			}
		}
	}
	return 1;
}

int main(void) {
	int N, M; scanf("%d %d", &N, &M);
	int** matrix = (int**)malloc(sizeof(int*) * N);
	for (int i = 0; i < N; i++)
		matrix[i] = (int*)malloc(sizeof(int) * M);

	getMatrixInput(matrix, N, M);

	int side = solve(matrix, N, M);
	printf("%d", side * side);

	for (int i = 0; i < N; i++)
		free(matrix[i]);
	free(matrix);

	return 0;
}