[백준 - C#] 1051번 숫자 정사각형

문제링크

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

1051번: 숫자 정사각형

 

문제

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

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

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

출력

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

 

문제정리

1. N×M 크기의 직사각형이 존재한다.
2. 직사각형에서 꼭짓점에 쓰여있는 숫자가 모두 같은 가장 큰 정사각형을 찾아야한다.

이번 문제의 경우 직사각형안에서 존재하는 정사각형 중 꼭짓점이 모두 같으면서 가장 큰 정사각형을 찾는 문제입니다.

저는 처음 [0,0] 부터 [N,M] 까지 전부 비교하여 모든 정사각형을 다 검사하고 값을 찾아내었습니다.

 

처음 반복문을 돌며 [x, y] 의 x 값을 먼저 증가 시켜주고 x 값이 N보다 크거나 같아진다면 x값을 0으로 초기화하고 y값을 늘려주었습니다. 만약 x와 y 값이 N,M을 벗어나지 않는다면 꼭짓점이 같은지 검색하고 같으면 SIZE의 크기를 비교하고 교체해주었습니다.

 

더 자세한 코드는 아래 자세히 나와있습니다! 

C# 코드

static void Main(string[] args)
{
    // 1051
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
 
    int N = int.Parse(input[0]);
    int M = int.Parse(input[1]);
    int[,] rectangle = new int[N, M];
 
    for (int i = 0; i < N; i++)
    {
        char[] row = reader.ReadLine().ToCharArray();
        for (int j = 0; j < M; j++)
            rectangle[i, j] = int.Parse(row[j].ToString()); // N*M의 직사각형 값 할당
    }
 
    int x = 0;
    int y = 0;
    int size = 0;
    int index = 1;
 
    while (true)
    {
        if (x + index >= N || y + index >= M) // x와 y의 값이 N이나 M을 벗어나면 
        {
            x++;
 
            if (x >= N) // x 값이 N보다 크거나 같으면 초기화 하고 y 증가
            {
                x = 0;
                y++;
            }
 
            if (y >= M) // y 값이 M보다 크거나 같으면 반복문 종료
                break;
 
            index = 0;
        }
 
        // 각 꼭지점의 값이 같은지 확인
        if (index != 0 && rectangle[x, y] == rectangle[x + index, y + index] &&
            rectangle[x + index, y + index] == rectangle[x + index, y] &&
            rectangle[x + index, y] == rectangle[x, y + index])
        {
            // 정사각형의 크기 계산
            if (size < (index + 1) * (index + 1))
                size = (index + 1) * (index + 1);
        }
 
        index++;
 
    }
 
    if (size == 0)
        size = 1;
 
    writer.WriteLine(size);
 
    writer.Close();
    reader.Close();
}

 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.