[백준] 1051번. 숫자 정사각형(JAVA)

문제

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

---

풀이(11분)

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

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][m];
        for(int i = 0; i < n; i++){
            String temp = br.readLine();
            for(int j = 0; j < m; j++){
                arr[i][j] = Integer.parseInt(temp.substring(j,j+1));
            }
        }

        int max = Math.min(n,m);
        int answer = max;

        while(answer > 1){
            for(int i = 0; i <= n - max; i++){
                for(int j = 0; j <= m - max; j++){
                    int leftUnder = arr[i][j];
                    int rightUnder = arr[i+max-1][j];
                    int leftOver = arr[i][j+max-1];
                    int rightOver = arr[i+max-1][j+max-1];

                    if(leftUnder == rightUnder){
                        if(leftUnder == leftOver){
                            if(leftUnder == rightOver){
                                answer = max;
                                System.out.println(answer*answer);
                                return;
                            }
                        }
                    }
                }
            }
            max--;
        }

        System.out.println(1);

    }
}

 

n x m 사각형 중에 정사각형을 만들 수 있는 최대의 값은 n과 m 중 더 작은 값을 이용하는 것이다.

 

즉, 최대 크기의 정사각형부터 후보를 두고, 하나씩 줄여가며 찾는 방식이다.

 

필수적으로 최대 크기의 사각형까지 보기 위해 1부터 찾아가는 것이 아닌, 최대부터 줄여오며 정답을 찾는 즉시 출력하는 것을 목표로 했다.