문제

이해

NxM 크기의 직사각형의 각 칸에는 숫자가 있다.

각 꼭짓점에 적혀 있는 수가 모두 같은 정사각형의 최대 크기를 구하면 된다.

접근

단순하게 문제에서 원하는 대로 구현하면 될 것 같다.

N과 M은 50보다 작은 자연수이기 때문에 탐색에 많은 반복이 필요하지는 않을 것 같다.

정사각형의 최대 크기를 구해야 하기 때문에 탐색하는 정사각형 한 변의 길이를 1부터 시작하기 보다는 직사각형 내에서 만들 수 있는 가장 큰 정사각형부터 탐색하는 것이 좋아보인다.

N, M 크기인 직사각형에서 만들 수 있는 가장 큰 정사각형의 한 변의 길이는 N과 M중 작은 값이 된다.

코드

package java_baekjoon;

import java.util.*;
import java.io.*;

public class prob1051 {
    static int N;
    static int M;
    static int[][] square;
    static int square_size;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        square = new int[N][M];
        square_size = Math.min(N, M);

        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                square[i][j] = input.charAt(j) - '0';
            }
        }
        
        for (;square_size > 0;square_size--) {
            if (isPossible(square_size)) {
                break;
            }
        }

        System.out.println(square_size * square_size);
    }

    static boolean isPossible(int size) {
        for (int i = 0; i <= N - size; i++) {
            for (int j = 0; j <= M - size; j++) {
                int start_number = square[i][j];

                if (square[i + size - 1][j] == start_number && square[i][j + size - 1] == start_number
                        && square[i + size - 1][j + size - 1] == start_number) {
                    return true;
                }
            }
        }
        return false;
    }
}

결과