백준 1051 - 숫자 정사각형

C++

1051 번 - 숫자 정사각형

문제

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

접근 방법

코드

#include <iostream> 
#include <vector>   
#include <algorithm>

using namespace std;

int n, m, answer = 1; //점 하나만 있어도 크기는 1이다 38% -> 100%
int field[100][100];

void chk(int y, int x);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    string str;     //공백없이 숫자가 주어지므로, n개의 숫자 문자열을 받는다.
    for (int i = 0; i < n; i++) {
        cin >> str;
        for (int j = 0; j < m; j++) {
            field[i][j] = str[j] - '0';         //아스키 코드를 이용하여 숫자 문자를 int로 변환
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            chk(i, j);                      //각 좌표마다 정사각형을 만들기 시작
        }
    }
    cout << answer;
}

void chk(int y, int x) {
    int dis = 1, result = 0;        //dis는 정사각형 크기, dis = 1인 2x2 크기의 정사각형 부터 시작한다. result = 0으로 설정 25% -> 38%
    int limit = min(n, m);
    int curN = field[y][x];     //기준이 되는 왼쪽 위 꼭지점
    while (dis < limit) {
        if (y + dis >= n || x + dis >= m)       //정사각형 꼭지점이 그래프의 크기를 넘을 경우를 대비 / 채점 5%->25%
            break;
        //아래, 대각선, 오른쪽 꼭지점이 다 같은지 확인
        if (curN == field[y + dis][x] && curN == field[y + dis][x + dis] && curN == field[y][x + dis])
            result = (dis + 1) * (dis + 1);     //정사각형 크기를 저장한다.
        dis++;                                  //정사각형 크기 증가
    }
    answer = max(result, answer);
}

후기 및 개선할 점

3가지의 이유로 틀렸다는 결과를 얻었다.

1. 처음 주어진 직사각형 크기를 벗어나게 정사각형을 생성
2. 한 점에서 정사각형을 못 찾으면, 0을 반환하여야 하는데, 정사각형의 크기를 담는 변수를 초기화 하지 않아 쓰레기값이 결과로 나옴
3. 점 하나만 있으도 크기는 1이다. 2번에서 생각 한 것 처럼, 정사각형을 찾지 못하면 0을 반환하였는데, 점하나도 정사각형이라고 생각하여 문제의 답을 나타내는 answer를 1로 초기화 하여야 한다.