[99클럽 5기 코테 스터디 TIL 12일차] 숫자 정사각형 (feat. 완전탐색)

1) 문제

https://www.acmicpc.net/problem/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

 

 

2) 문제 풀이

1. 입력 처리
   • Scanner를 사용하여 N과 M을 입력받음
   • grid 배열을 선언하고, 문자열을 한 줄씩 입력받아 2차원 char 배열로 저장함
2. 최대 정사각형 찾기
   • 가능한 최대 변의 길이를 min(N, M)으로 설정하고, 1부터 시작하여 점점 큰 크기의 정사각형을 검사함
   • (i, j)를 왼쪽 위 꼭짓점으로 설정하고, (i + size - 1, j + size - 1)을 오른쪽 아래 꼭짓점으로 하는 정사각형을 확인함
   • 네 꼭짓점의 값이 같다면 해당 크기의 정사각형을 정답 후보로 업데이트함
3. 출력
   • 가장 큰 정사각형의 넓이 (size * size)를 출력함

시간 복잡도

• 최악의 경우 O(NM⋅min⁡(N,M))O(NM \cdot \min(N, M))O(NM⋅min(N,M))이지만, 큰 크기부터 검사하므로 평균적인 실행 시간은 훨씬 빠름

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        sc.nextLine(); // 개행 문자 제거

        char[][] grid = new char[N][M];
        for (int i = 0; i < N; i++) {
            grid[i] = sc.nextLine().toCharArray();
        }
        sc.close();

        int maxSize = 1; // 최소 정사각형 크기는 1x1
        
        // 가능한 최대 변의 길이부터 검사
        int maxLen = Math.min(N, M);
        for (int size = maxLen; size >= 1; size--) {
            for (int i = 0; i <= N - size; i++) {
                for (int j = 0; j <= M - size; j++) {
                    // 꼭짓점 확인
                    if (grid[i][j] == grid[i][j + size - 1] &&
                        grid[i][j] == grid[i + size - 1][j] &&
                        grid[i][j] == grid[i + size - 1][j + size - 1]) {
                        maxSize = Math.max(maxSize, size * size);
                    }
                }
            }
        }
        
        System.out.println(maxSize);
    }
}