백준 1051 : 숫자 정사각형

문제 링크입니다 https://www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

 

입력받은 N*M 크기의 직사각형 배열 전체를 탐색하면서, 정사각형 한 변의 길이를 늘려가며 네 꼭짓점의 값이 같은 정사각형을 찾아 그 정사각형의 크기를 찾는식으로 해결했습니다. 자세한 풀이 방법은 주석을 참고해주세요.

 

 

[소스코드]

 

#include<cstdio>
const int MAX = 50 + 10;
 
int n, m, map[MAX][MAX];
 
int main(void) {
 
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            
            // %1d로 입력을 받으면 띄어쓰기가 되지 않은 숫자들을
            // 하나씩 입력받을 수 있습니다
            scanf("%1d", &map[i][j]);
        }
 
    // 정사각형이기 때문에 한 변의 최대 길이는 n과 m중 작은놈입니다
    int max = n < m ? n : m;
 
    // 찾고자 하는 정사각형이 없으면 칸 하나도 정사각형이므로
    // 1을 출력하기 위해 초기값 1로 설정합니다
    int ret = 1;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            
            // k는 정사각형의 한 변을 k만큼 늘려가면서 찾아보기 위함
            for (int k = 1; k <= max; k++) {
 
                // 세로의 길이는 n보다 작아야 하고, 가로의 길이는 m보다 작아야 하며
                // 정사각형의 네 꼭짓점의 값이 모두 같다면
                if (i + k < n && j + k < m && map[i][j] == map[i + k][j] 
                    && map[i + k][j] == map[i][j + k]
                    && map[i][j + k] == map[i + k][j + k]) {
 
                    // 그때의 정사각형 크기를 ret에 담아줍니다
                    if (ret < (k + 1)*(k + 1)) ret = (k + 1)*(k + 1);
                }
            }
        }
    }
    // for문 안의 if문에 걸리지 않았으면 1을 출력할 것입니다
    printf("%d", ret);
    return 0;
}