[BOJ S3][#구현]1051번 숫자 정사각형

숫자 정사각형 성공

 

문제

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

입력

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

출력

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

예제 입력 1 복사

3 5
42101
22100
22101

예제 출력 1 복사

9

예제 입력 2 복사

2 2
12
34

예제 출력 2 복사

1

예제 입력 3 복사

2 4
1255
3455

예제 출력 3 복사

4

예제 입력 4 복사

1 10
1234567890

예제 출력 4 복사

1

예제 입력 5 복사

11 10
9785409507
2055103694
0861396761
3073207669
1233049493
2300248968
9769239548
7984130001
1670020095
8894239889
4053971072

예제 출력 5 복사

49

 

📝 접근법 

• 간단한 구현 문제로 직사각형에서 모든 가능한 정사각형을 검사하면서 최대 크기의 정사각형을 찾으면 된다.
• 해결 방안
  • 브루트 포스 알고리즘
  • 최적화를 위하 DP 사용도 가능하지만 이번에는 구현하지 않았습니다. (공부 부족 문제)

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

public 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());

        char[][] rect = new char[n][m];
        for (int i = 0; i < n; i++) {
            rect[i] = br.readLine().toCharArray();
        }
        int maxSquareSize = 1;

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                for(int k = 1; k <= Math.min(n-i, m-j); k++){
                    if(rect[i][j] == rect[i][j+k-1]&& rect[i][j] == rect[i+k-1][j]&& rect[i][j] == rect[i+k-1][j+k-1]){
                        maxSquareSize = Math.max(maxSquareSize, k*k);
                    }
                }
            }
        }

        // 결과 출력
        System.out.println(maxSquareSize);
    }
}

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

 

 

중요 코드만 보자

for(int i = 0; i < n; i++){// 직사각형의 모든 행을 조회
    for(int j = 0; j < m; j++){ // 해당 행에 대한 모든 열 조회
        for(int k = 1; k <= Math.min(n-i, m-j); k++){ //해당 위치에서 만들 수 있는 최대 크기 직사각형까지 검사
           if(rect[i][j] == rect[i][j+k-1]&& rect[i][j] == rect[i+k-1][j]&& rect[i][j] == rect[i+k-1][j+k-1]){
               maxSquareSize = Math.max(maxSquareSize, k*k);
           }
        }
    }
}