공부 자료/알고리즘
(C/C++) 백준 1051 번 - 숫자 정사각형
뚜루뚜루세니
2021. 7. 14. 12:11
728x90
문제 출처: https://www.acmicpc.net/problem/1051
1051번: 숫자 정사각형
N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는
www.acmicpc.net
1. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int n, m; //n 가로 m 세로
int arr[50][50];
int Square(void) {
int result = 1;
int size = min(n, m); //정사각형 길이 중 최대로 긴 것
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 1; k < size; k++) {
if (i + k < n && j + k < m && arr[i + k][j] == arr[i][j] && arr[i + k][j + k] == arr[i][j] && arr[i][j + k] == arr[i][j]) {
result = max(result, k + 1);
}
}
}
}
return result * result;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%1d", &arr[i][j]);
}
}
printf("%d", Square());
}
|
cs |
2. 해결과정
처음에 직사각형의 가로 세로 길이를 입력을 받는다. 직사각형 내에서 정사각형을 뽑아낼 때 최대로 정사각형의 길이는 min(n,m)으로 둘 중에 길이가 작은 변이 정사각형의 가장 긴 길이라고 생각을 할 수 있다. 그러한 size을 기준으로 입력한 수가 동일한지 탐색을 해주면 된다.
3. 느낀점
길이가 1인 정사각형이 최소이기 때문에 처음에 result를 1로 초기화 했었는데 그것을 놓쳐서 계속 오류가 났었다. 그것을 해결하는 것에 애를 먹었다.
728x90