[C언어] 백준 1051번: 숫자 정사각형

• 문제

백준 1051번: 숫자 정사각형

https://www.acmicpc.net/problem/1051

 

문제

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

 

입력

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

 

출력

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

---

• 코드

#include <stdio.h>
// 백준 1051번: 숫자 정사각형
int main(){

    int n,m;
    scanf("%d %d", &n, &m);

    int arr[n][m];

    char temp[m + 1];

    for(int i = 0; i < n; i++){
        scanf("%s", temp);
        for(int j = 0; j < m; j++){
            arr[i][j] = temp[j] - '0';
        }
    }

    int width = 1;

    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < m - 1; j++){
            for(int k = 1; ; k++){
                if((i + k >= n) || (j + k >= m)){
                    break;
                }
                if((arr[i][j] == arr[i + k][j]) && (arr[i][j] == arr[i][j + k]) && (arr[i][j] == arr[i + k][j + k])){
                    if((k + 1) * (k + 1) > width){
                        width = (k + 1) * (k + 1);
                    }
                }
            }
        }
    }

    printf("%d\n", width);

    return 0;
}

---

• 문제풀이방법

1. n x m 크기의 2차원배열을 만든다.
2. 숫자를 붙여서 주기에 문자열로 숫자를 받아들인 후 배열에 저장한다.
3. 3중 for문을 활용하여 모든 경우를 탐색한다. - 브루트포스
4. 만약 i + k >= m 혹은 k + k >= m 이면 배열을 초과하기에 break
5. 만약 네 변 모두 길이가 같으면 넓이를 구한다.
6. 넓이가 width(넓이 변수 1로 설정 함) 보다 크면 width를 5 에서 구한 넓이로 바꾼다.
7. 반복문이 끝난 후 width 출력