[백준] 1051번 -숫자 정사각형 (자바 풀이)

문제

1051번: 숫자 정사각형

풀이

1. N, M이 50 이하로 작다.

2. 꼭짓점을 살펴보기 위해서는 기준점에서 3군데만 찾아보면 된다. 

3. N과 M중 더 작은 수가 정사각형의 최대길이다.

4. 따라서 최대 50(N)*50(M)*3(꼭짓점 3개 비교)*50(정사각형의 최대 길이) 번의 연산이 필요하므로 브루트포스 방식이 가능하다!

 

 

풀이법은 간단하다. 정사각형의 최대 길이는 N과 M 중 더 작은 것일 것이다. 이것을 len이라고 하자.

매번 모든 원소를 조사할 필요 없이 세로는 N-len, 가로는 M-len 까지만 조사하면 된다.

그 이상은 배열의 범위를 벗어나기 때문이다.

따라서 for문을 돌면서 기준점과 세 꼭짓점을 비교해 모두 같다면 len*len을 출력하고 종료하면 된다.

가능한 가장 긴 길이부터 탐색을 시작했으니 무조건 최댓값이므로 종료해도 되는 것이다.

 

만약 N-len, M-len까지 모두 조사했는데 정사각형이 존재하지 않으면 len을 1 줄여서 계속 찾으면 된다.

 

코드를 보면 이해가 더 쉬울 것이다.

코드

import java.io.*;
import java.util.*;
 
public class Baekjoon_1051 {
    static int N,M, ans=Integer.MIN_VALUE;
    static int[][] map;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        
        int len = Math.min(N, M);
        // 정사각형의 최대 길이는 N과 M 중 더 작은 것
        
        while(len > 1) {
            for(int i=0; i<= N-len; i++) {
                for(int j=0; j<=M-len; j++) {
                    int num = map[i][j];
                    // 꼭짓점 3군데 비교
                    if(num==map[i][j+len-1] && num == map[i+len-1][j] && num == map[i+len-1][j+len-1]) {
                        System.out.println(len*len);
                        return;
                    }
                }
            }
            len--;
        }
        
        System.out.println(len*len);
        
    }
 
}