[Baekjoon/C++] 1051번 - 숫자 정사각형

Baekjoon Online Judge

문제로 이동

 

문제

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

 

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

 

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

 

---

예제 입력	예제 출력
3 5 42101 22100 22101	9
2 2 12 34	1
2 4 1255 3455	4
1 10 1234567890	1
11 10 9785409507 2055103694 0861396761 3073207669 1233049493 2300248968 9769239548 7984130001 1670020095 8894239889 4053971072	49

---

풀이

#include <iostream>
using namespace std;

int main() {
	string nemo[51];

	int N, M; // N×M크기의 직사각형
	cin >> N >> M;

	// 입력
	for (int i = 0; i < N; i++)
		cin >> nemo[i];

	int nemoSize = 1; // 네모의 크기

	// 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			char c1 = nemo[i][j]; // 정사각형의 왼쪽 위 꼭짓점

			for (int k = j + 1; k < M; k++) {
				char c2 = nemo[i][k]; // 정사각형의 오른쪽 위 꼭짓점

				if (c1 == c2) {
					int idx = k - j; // 정사각형의 윗꼭짓점 사이의 거리

					// 범위를 벗어남
					if (idx + i >= N) break;

					// 전에 찾았던 것보다 큰 정사각형을 찾음
					if (nemo[idx + i][j] == c1 && nemo[idx + i][k] == c2 && idx + 1 > nemoSize)
						nemoSize = idx + 1;
				}
			}
		}
	}

	// 출력
	printf("%d\n", nemoSize * nemoSize);

	return 0;
}

ex)
i|j	01234

0	42101	1. c1 = nemo[0][2], c2 = nemo[0][4]라고 하면 두 숫자 사이의 거리는 2
1	22100	2. nemo[2][2]와 nemo[2][4]의 숫자 확인 -> 둘 다 1
2	22101	3. 숫자 정사각형의 크기 = (2 + 1) * (2 + 1) = 9