백준 문제풀이 - 1051 번

링크 -> https://www.acmicpc.net/problem/1051

1. 요약 및 풀이방법

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

ex)

• 입력

3 5
42101
22100
22101

인 경우

101
100
101

위의 사각형이 꼭짓점에 쓰여있는 수가 모두 같으면서 가장 큰 정사각형이다.

• 출력

9

가장 큰 정사각형을 찾아야 하므로,
rol, col 중 작은 값을 한 변의 초기값으로 두고
네개의 꼭짓점의 값이 동일한지 확인한다.
조건을 만족하는 정사각형이 없으면 한 변의 크기를 1씩 감소하면서 같은 작업을 하므로
재귀를 이용한다.
이때 조건을 만족하는 정사각형을 찾거나, 변의 크기가 1이 되면 재귀를 멈추고 return 한다.

2. Code

#include <iostream>
#include <vector>

std::vector<std::string> g_rec;
int g_row, g_col, g_answer;

void input()
{
    std::string tmp;

    std::cin >> g_row >> g_col;
    g_answer = std::min(g_row, g_col);
    for (int i = 0; i < g_row; i++)
    {
        std::cin >> tmp;
        g_rec.push_back(tmp);
    }
}

void solution()
{
    if (g_answer == 1)
        return ;
    for (int i = 0; i < g_row - g_answer + 1; i++)
    {
        for (int j = 0; j < g_col - g_answer + 1; j++)
        {
            if (g_rec[i][j] == g_rec[i][j + g_answer - 1] &&
                g_rec[i + g_answer - 1][j] == g_rec[i + g_answer - 1][j + g_answer - 1] &&
                g_rec[i][j] == g_rec[i + g_answer - 1][j])
            {
                return ;
            }
        }
    }
    g_answer--;
    solution();
}

void print()
{
    std::cout << g_answer * g_answer << std::endl;
}

int main()
{
    input();
    solution();
    print();
    return (0);
}

3. 학습 내용

네 꼭짓점의 값이 동일한지 확인하는 로직이 최선인지는 모르겠으나,
재귀함수 형태를 연습할 수 있었다.

4. 결과