[백준 / Java] 1051번: 숫자 정사각형 (브루트포스 알고리즘)

 

코테99 11일차 문제는 백준 1051번 '숫자 정사각형'이다.

 

 

이번 문제도 완전 탐색 (브루트포스) 알고리즘을 활용하는 문제였다.

 

 

접근 방법

1. 꼭짓점에에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는다.
2. 정사각형은 행 또는 열에 평행해야 한다.

알고리즘 진행 순서

1. 입력된 값을 배열에 넣는다.
2. 전체(N*M)를 도는데, 가능한 최대 정사각형 크기 안에서 반복하여 최대 정사각형을 구한다.
3. 최대 정사각형을 출력한다.

구현 코드

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

public class Main {
    static int[][] arr;
    static int N, M = 0;
    // 최소 정사각형 크기 => 이후 최대값을 넣을 것.
    static int maxSize = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];

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


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 가능한 최대 정사각형 크기
                int maxLength = Math.min(N - i, M - j);

                for (int k = 1; k < maxLength; k++) { // k는 현재 변의 길이, 점점 늘리면서 다 살펴보기
                    if (arr[i][j] == arr[i + k][j] && arr[i][j] == arr[i][j + k] && arr[i][j] == arr[i + k][j + k]) {
                        maxSize = Math.max(maxSize, (k + 1) * (k + 1)); // 최대 값을 집어 넣기
                    }
                }
            }
        }
        System.out.println(maxSize);

    }

}

 

회고

1. 처음에 브루트포스 구현에 익숙하지 않아서 단순히 생각하지 않고 한 줄에서 중복을 찾고 거리와 값을 저장하려고 했다.
2. 최소 정사각형 크기와 최대 정사각형 크기를 기준으로 하는 것을 생각하지 못했다. 연습이 많이 필요할 것 같다.