[백준/C++] 1051번. 숫자 정사각형

문제

1051번: 숫자 정사각형

---

1. 첫 번째 풀이 (마지막 풀이)

사고 과정

- 일단 맨 왼쪽 위에서 시작, 정사각형을 찾는다.

- 가장 큰 정사각형을 찾는 것이므로, M에서부터 1씩 줄여가며 숫자가 같은지 검사

- 맨 첫 줄에서 사각형이 안 만들어진다면, 다음 줄로 넘어가 반복

- N, M은 최대 50이니 오래 걸리지 않을 것 같다.

- 크기가 가장 큰 사각형을 찾았을 때 종료해야 하므로, 예를 들어 5 5라면 크기가 25인 경우, 16인 경우, 9인 경우... 순으로 비교하는 게 맞는 것 같다.

 

1. 입력값 저장 (띄어쓰기가 없으니 scanf 사용)

2. 정수 k를 N, M 중 작은 값으로 초기화

3. 반복문 작성, k를 1씩 줄여가며 가장 큰 정사각형을 찾는다.

4. 정사각형은 맨 왼쪽 위에서 시작, 오른쪽으로 이동하며 찾는다. 한 줄을 전부 검색했다면 아래로 이동해 다시 찾는다.

 

이후 작성할 글이 있다면 추가 작성

 

코드

#include <stdio.h>
#include <vector>

int main() {
	int N, M, s;
	scanf("%d %d", &N, &M);

	std::vector<std::vector<int>> grid(N, std::vector<int>(M, 0));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &s);
			grid[i][j] = s;
		}
	}

	int k = (N > M) ? M - 1 : N - 1;

	do {
		for (int i = 0; i < N; i++) {
			if (i + k >= N) {
				break;
			}

			for (int j = 0; j < M; j++) {
				if (j + k >= M) {
					break;
				}

				if (grid[i][j] == grid[i][j + k] 
					&& grid[i][j] == grid[i + k][j] 
					&& grid[i][j] == grid[i + k][j + k]) {
					printf("%d", (k + 1) * (k + 1));

					return 0;
				}
			}
		}
	} while (--k);

	printf("1");
}프로그램 코드

 

결과

결과는 성공

---

개선

사고 과정

- 코드가 길지만, 딱히 입력부나 탐색부나 건드릴 부분은 없어보인다. 중괄호를 빼는 등 의도적으로 줄일 순 있지만, 가독성은 이쪽이 더 좋은 편

---

가장 효율적인 코드

https://www.acmicpc.net/source/3631800

ilsanzzang님의 코드. 비슷한 흐름이다.

 

내 코드와 비교

1. 벡터 대신 배열을 사용하며, 크기는 99로 고정해두셨다.

2. 입력을 받을 때, scanf에 직접 배열 주소를 넣으셨다. 나는 변수 하나에 받아둔 후 배열에 대입했다.

3. s = n + m으로 두시고, for문 내에선 i + s < n으로 작성하셨다. 이를 통해 s가 n, m보다 클 때는 감소만, 둘 중 작은 값에 도달했을 때부터 비교를 실행한다. ...천잰데?

---

강평

N과 M이 최대 50밖에 되지 않아 쉽게 풀린 문제. 하지만 세상은 넓고 고수는 많았다.