[Algorithm] boj_1051_숫자 정사각형 (bruteForce)

문제

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

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

입력

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

출력

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

예제 입력 1

3 5
42101
22100
22101

예제 출력 1

9

---

풀이

만일 N = 4, M = 3 이라고 가정하자.

1 2 3 4
1 2 3 4
1 2 3 4

탐색 방법

여기서 가능한 정사각형의 최대 넓이는 3x3 = 9이다.
그리고 탐색할 기준점은 [0][0], [0][1] 뿐이다.

만일 가능한 3x3 크기의 정사각형이 없는 경우라고 해보자.
그럼 두번째 최대 넓이는 2x2 = 4이다.

그럼 탐색할 곳은 [0][0], [0][1], [0][2], [1][0], [1][1], [1][2] 가 된다.

따라서 현재 구하는 변의 길이를 size라고 할때,
-> 탐색은 [0][0] ~ [row-size][col-size] 까지 하면 된다.

그리고, 탐색은 가장 큰 넓이가 나올수 있는 경우부터 탐색한다.
-> 정사각형을 찾으면 그게 답이 된다.

---

정사각형 판별 방법

4개의 변에 있는 수가 모두 같은 수여야 하기 때문에, 다음과 같은 식이 나온다. (standard : 현재 탐색중인 꼭짓점)

(standard == rectangle[r + size - 1][c]
&& standard == rectangle[r][c + size - 1]
&& standard == rectangle[r + size - 1][c + size - 1]);

---

코드

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

public class boj_1051_bruteForce {

    static int row, col;
    static int[][] rectangle;
    static int size;
    static boolean hasFound;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        row = Integer.parseInt(s[0]);
        col = Integer.parseInt(s[1]);
        size = Math.min(col, row);

        rectangle = new int[row][col];
        for (int i = 0; i < row; i++) {
            String[] split = br.readLine().split("");

            for (int k = 0; k < col; k++) {
                rectangle[i][k] = Integer.parseInt(split[k]);
            }
        }

        while (size > 1) {
            for (int i = 0; i <= row - size; i++) {
                for (int k = 0; k <= col - size; k++) {
                    if(search(i, k, size)) {
                        hasFound = true;
                        break;
                    }
                }

                if(hasFound) break;
            }

            if(hasFound) break;
            size--;
        }

        System.out.println(size * size);
    }

    static boolean search(int r, int c, int size) {
        int standard = rectangle[r][c];

        return (standard == rectangle[r + size - 1][c]
                && standard == rectangle[r][c + size - 1]
                && standard == rectangle[r + size - 1][c + size - 1]);
    }
}