문제 푼 날짜 : 2021-09-29

문제

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

접근 및 풀이

완전 탐색으로 풀 수 있는 문제였고, 아래의 생각대로 코드를 구현하였다.

1. 주어진 직사각형의 모든 좌표를 찾아본다.
2. 해당 좌표에서 행과 열의 길이 중 더 짧은 길이만큼 변의 길이를 늘려본다.
   2-1. 이 때 변에 해당하는 모든 좌표는 살펴볼 필요가 없고, 꼭짓점만 확인해준다.
3. 모든 꼭짓점이 같을 때, 해당 정사각형이 가지는 변의 길이를 최댓값으로 계속 업데이트해주었다.

코드

// 백준 1051번 : 숫자 정사각형
#include <iostream>

using namespace std;

int main() {
    int N, M, ans = 1;
    cin >> N >> M;

    int arr[51][51];

    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < M; j++) {
            arr[i][j] = str[j] - '0';
        }
    }
    int scope = N > M ? M : N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int cnt = 1;
            int corner = arr[i][j];

            while (cnt < scope) {
                if (i + cnt < N && j + cnt < M) {
                    if (corner == arr[i][j + cnt] && corner == arr[i + cnt][j] && corner == arr[i + cnt][j + cnt]) {
                        ans = max(ans, cnt + 1);
                    }
                }
                cnt++;
            }
        }
    }
    cout << ans * ans;
    return 0;
}

결과

피드백

간단한 문제같아 보여도 조건처리할 때 세세하게 잘해줘야 한 번에 통과할 수 있는 것 같다.
문제 풀때마다 더 집중하자.