[백준] 1051_숫자정사각형

 

 

Sliver

 

 

문제

 

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다.

이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오.

이때, 정사각형은 행 또는 열에 평행해야 한다.

 

 

입력

 

첫째 줄에 N과 M이 주어진다.

N과 M은 50보다 작거나 같은 자연수이다.

둘째 줄부터 N개의 줄에 수가 주어진다.

 

 

출력

 

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

 

 

---

 

풀이

 

import java.util.*;
import java.lang.*;
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());
        String[][] arr = new String[N][M];
        for(int i=0; i<N; i++){
            arr[i] = br.readLine().split("");
        }

        int max = 1 ;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                // 정사각형의 크기를 키워가며 검사
                for(int k=1; (i+k)<N&& (j+k)<M; k++){
                    // 4개의 꼭지점이 모두 같은 숫자인지 검사 
                    if(arr[i][j].equals(arr[i][j+k])&&
                       arr[i][j].equals(arr[i+k][j])&&
                       arr[i][j].equals(arr[i+k][j+k]))
                        max = Math.max(max, k+1);
                }
            }
        }

        System.out.println(max*max);

        br.close();
    }

}

 

해결방법

 

1. 입력받은 값을 N*M 배열에 저장한다. 

 

2. 좌표(i, j) 에서부터 정사각형을 탐색한다.

• k를 증가시켜 정사각형의 크기를 키워가며 네 꼭짓점의 값이 동일한지 확인한다. 
• 꼭짓점의 값이 동일하면, 현재 정사각형의 크기와 max의 크기를 비교하여 업데이트한다. 

3. 사각형의 넓이를 구해야 하므로 (max * max) 를 리턴한다. 

 

 

 

 

---

 

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