[백준] 1051번 숫자 정사각형 C++ 풀이

---

알고리즘 분류

• 구현
• 브루트포스 알고리즘

---

문제 설명

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

---

입력 설명

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

---

출력 설명

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

---

예제 입력

3 5
42101
22100
22101

2 2
12
34

2 4
1255
3455

1 10
1234567890

11 10
9785409507
2055103694
0861396761
3073207669
1233049493
2300248968
9769239548
7984130001
1670020095
8894239889
4053971072

---

예제 출력

9

1

4

1

49

---

아이디어

가장 큰 정사각형을 찾아야 하기 때문에 해당 배열에서 만들 수 있는 가장 큰 정사각형의 사이즈부터 탐색을 시작해서 사이즈를 점점 줄여나간다.

정사각형의 4개의 꼭짓점의 좌표를 이동시켜 가며 가장 크고 각 꼭짓점의 숫자가 모두 동일한 정사각형을 찾아 사이즈를 제곱하여 정사각형의 넓이를 출력한다.

---

알고리즘

입력받은 N과M 중 더 작은 것을 size로 놓고 초기 좌푯값을 x1 = 0, x2 = size-1, y1=0, y2 = size-1 로 잡는다.

size가 1보다 크다면 계속 반복하는데 숫자를 저장한 배열 arr의 arr[x1][y1]==arr[x2][y1] && arr[x2][y1] == arr[x1][y2] && arr[x1][y2] == arr[x2][y2]이라면 size*size를 출력하고 종료한다. size가 1이라면 1을 출력하고 종료한다.

기본적으로는 y1과 y2를 증가시키면서 탐색을 진행하고 만약 y2가 배열 끝에 도달하면

다시 초깃값으로 설정하고 x1과 x2를 증가시키면서 탐색을 진행하고 x1과 y1이 모두 배열 끝에 도달하면 x와 y를 모두 초깃값으로 설정하고 size를 1 감소시키고 탐색을 계속 진행한다.

---

코드

#include <iostream>
#include <string>
using namespace std;
int main()
{
    int N,M,size;
    cin>>N>>M;
    int arr[N][M];
    for(int i=0;i<N;i++)
    {
        string str;
        cin>>str;
        for(int j=0;j<M;j++)
            arr[i][j] = str[j] - '0';
    }
    if(N<M) size = N;
    else size = M;
    int x1 = 0, x2 = size-1, y1=0, y2 = size-1;
    while(size > 1)
    {
        if(arr[x1][y1]==arr[x2][y1] && arr[x2][y1] == arr[x1][y2] && arr[x1][y2] == arr[x2][y2])
        {
            cout<<size*size;
            break;
        }
        else if(x2+1 == N && y2+1 == M)
        {
            size--;
            x1 = 0, x2 = size-1, y1=0, y2 = size-1;
        }
        else if(x2+1 == N)
        {
            y1++, y2++;
        }
        else if(y2+1 == M)
        {
            x1++, x2++;
            y1=0, y2 = size-1;
        }
        else y1++, y2++;
    }
    if(size==1)cout<<1;
    return 0;
}

---

후기

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

한 줄에 있는 숫자가 모두 이어져 있어서 이를 string으로 입력 받은 후 string의 각 칸 - '0'을 통해서 숫자로 바꿔서 저장했다. 처음에는 이를 인지하지 못해서 이상한 숫자가 저장되었다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!