[백준/JAVA] 🥈 1051번 숫자 정사각형

문제

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

입력

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

출력

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

예제 입출력

 

풀이

N 혹은 M이 1인 경우는 예제 입출력 4번처럼 숫자가 가로로 한 줄 있거나, 혹은 세로로 한 줄 있는 경우이다

이 경우에는 정사각형의 한 변의 최대 길이가 1이기 때문에 그냥 1을 리턴해준다.

 

N과 M이 2이상인 경우에는, 둘 중 작은 값이 정사각형 한 변의 최대 길이가 된다.

len=2부터 min(N,M)와 같을 때까지 정사각형의 한 변의 길이를 늘려가며 답을 탐색한다.

이때 한 변의 길이 len 값에 따라 NxM배열에서 접근 가능한 가로와 세로 길이가 결정된다.

 

아래 그림같은 경우에는 2x2정사각형을 만들고 있기 때문에

가로는 0부터 3까지, 세로는 0부터 1까지만 접근이 가능하다.

 

 

3x5 배열에서 정사각형 한 변의 길이가 3일 때 경우를 살펴보자.

이중 for문을 돌면서 i가 0, j가 0일 때는 아래의 사각형이 그려지고, 사각형의 네 꼭짓점의 좌표는 다음과 같다.

 

 

i가 0, j가 0일 때는 아래의 사각형이 그려지고, 사각형의 네 꼭짓점의 좌표는 다음과 같다.

두 예시를 통해 네 개의 꼭짓점을 i과 j을 사용한 식으로 도출하면 다음과 같고,

이때, 꼭 정사각형의 한 변의 길이를 고려해줘야 한다! 안그러고 a[i][j], a[i][j+1], a[i+1][j], a[i+1][j+1] 이런 식으로 접근하면 안된다.

 

네 개의 꼭짓점의 값이 모두 같을 경우 해당 사각형의 면적을 출력해주면 된다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static int[][] square;
    static int answer=1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        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] = Character.getNumericValue(row.charAt(j));
            }
        }
//        n과 m 중 최솟값이 정사각형 한 변의 길이 최댓값으로 가질 수 있다
        int minNum = Math.min(n, m);
        if(minNum==1) { //1이면 어차피 정답 1
            System.out.println(answer);
        }else System.out.println(findSquareArea(minNum));
    }

    static int findSquareArea(int minNum){
        for (int len = 2; len <= minNum; len++) { //정사각형 한 변의 길이를 가장 작은 수로 제한
            for (int i = 0; i <= n-len; i++) { //행 접근 가능 범위
                for (int j = 0; j <= m-len; j++) { //열 접근 가능 범위
                    if(  square[i][j] == square[i][j+(len-1)] && //꼭짓점에 있는 수가 모두 같다면
                            square[i][j+(len-1)] == square[i+(len-1)][j] &&
                            square[i+(len-1)][j] == square[i+(len-1)][j+(len-1)]  ){
                        answer=len*len; //넓이 담아주기~
                    }
                }
            }
        }
        return answer;
    }
}