백준 - [ 1051: 숫자 정사각형 ]

문제

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

입력

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

출력

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

예제 입력 1 

3 5
42101
22100
22101

예제 출력 1 

9

예제 입력 2 

2 2
12
34

예제 출력 2 

1

 

 

---

정사각형 크기 2부터 시작해서, [0][0] 부터 시작해서 행과 열을 한 칸씩 옮겨가며 해당 크기의 정사각형에서 네 꼭지점이 모두 동일한지 확인하도록 했다.

만약 해당 크기의 정사각형을 찾았으면, go-to 문으로 다음 크기의 정사각형을 찾도록 했다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] square = new int[N][M];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                square[i][j] = str.charAt(j) - '0';
            }
        }

        int answer = 1;
        int max = N > M ? N : M;
        out:
        for (int k = 2; k <= max; k++) { // 정사각형 크기
            for (int i = 0; i < N; i++) { // 행
                for (int j = 0; j < M; j++) { // 열
                    if (M >= j + k && N >= i + k) { // 정사각형 만들 공간 있으면
                        int point = square[i][j];
                        if (point == square[i][j + k - 1] && point == square[i + k - 1][j] // 꼭지점 값 같으면
                                && point == square[i + k - 1][j + k - 1]) {
                            answer = k;
                            continue out;
                        }
                    }
                }
            }
        }

        bw.write(answer * answer + "");
        bw.flush();
        bw.close();
        br.close();

    }
}

 

 

---