[BOJ][완전탐색] 1051. 숫자 정사각형 (java)

✏️ 문제

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

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

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

 

🔢 알고리즘

 

#완전탐색  #구현  #브루트포스

 

 

🤯 풀이 방법

가장 작은 정사각형은 1x1 크기이므로 기준을 잡고 2x2 정사각형부터 탐색한다.

정사각형 한 변의 최대값은 N과 M 중 작은 값이다.

2에서 N과 M중 작은 값까지 정사각형의 길이 기준으로 for문을 돌리고,

그 안에서 시작점 범위를 정해 이중 for문을 돌린다.

이때 확인할 값은 시작점 기준으로 오른쪽 + 길이, 아래 + 길이, 오른쪽 아래 대각선 값이다.

인덱스 범위 맞추는 데에 시간이 오래 걸렸다.. 🥲

 

👾 구현 코드 (자바)

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]); // 행의 수 N
        int M = Integer.parseInt(input[1]); // 열의 수 M
        int MAX = Math.min(N, M);   // 정사각형 한 변의 최대값은 N과 M중 작은 값
        int ans = 1;

        int[][] square = new int[N][M];

        for (int i = 0; i < N; i++) {
            String row = br.readLine();
            for (int j = 0; j < M; j++) {
                square[i][j] = row.charAt(j) - '0';
            }
        }

        for (int i = 2; i <= MAX; i++) { // 정사각형 크기 2~최대값 탐색
            for (int n = 0; n < N - i + 1; n++) {
                for (int m = 0; m < M - i + 1; m++) {
                    int start = square[n][m];
                    if (start == square[n + i - 1][m] && start == square[n][m + i - 1] && start == square[n + i - 1][m + i - 1]) {
                        ans = Math.max(ans, i);
                        break;
                    }

                }
            }
        }

        System.out.println(ans * ans);	// 출력은 정사각형의 넓이
    }
}

 

 

🤖 GPT의 제안