백준 1051번 숫자 정사각형 JAVA

링크텍스트

설명

arr[i][j]==arr[i+size][j] && arr[i][j] == arr[i][j+size] && arr[i][j] == arr[i+size][j+size]를 이용해 각 꼭지점이 같은지 확인하면 된다.
시간복잡도: O(N³), 공간복잡도: O(N*M)

코드

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

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 s = br.readLine();
	        for(int j=0;j<m;j++){
	            arr[i][j] = s.charAt(j) - '0';
	        }
	    }

		int maxSize = 1;
		int maxLen = Math.min(n, m);

		for(int size=1;size<maxLen;size++){
			for(int i=0;i+size<n;i++){
				for(int j=0;j+size<m;j++){
					if(arr[i][j]==arr[i+size][j] && arr[i][j] == arr[i][j+size] && arr[i][j] == arr[i+size][j+size]){
						maxSize = Math.max(maxSize, (size+1)*(size+1));
					}
				}
			}
		}

		System.out.println(maxSize);
	}
}