[TIL-25/02/04] 99클럽 코테 스터디 12일차 - 백준 1051: 숫자 정사각형 - JAVA

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

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

3 5
42101
22100
22101

 

예제 출력 1

9

 

문제 접근

완전 탐색 문제이다.

 

완전 탐색을 유추할 수 있는 포인트가 입력값 `NxM`의 범위가 `50`으로 작다. 최대 크기가 50×50(=2500)이므로 모든 경우를 탐색해도 충분히 가능하다.

 

2초라는 제한시간이 주어지고, 완전 탐색을 사용해도 `O(N³)`수준이라 문제없다.

 

문제의 핵심 패턴

이 문제의 핵심은 정사각형을 어떤 방식으로 찾아갈 것인가이다.

1. 입력값을 담은 입력 배열 `int[][] board`을 사용하며, `(0,0)`을 시작점으로 탐색을 시작한다.

2. 정사각형 크기를 이용하며 탐색을 진행하며, `1x1`부터 점점 키워가면서 탐색을 진행한다.

3. 정사각형의 꼭짓점(네 개의 꼭짓점 값)이 모두 같은 경우에만 유효한 정사각형이다. 

4. 정사각형 크기는 `1 ≤ k ≤ min(N, M)`이며, 시작점인 `(i, j)`가 좌상단 꼭짓점이라면 `i+k < N, j+k < M`을 만족해야 한다.

 

이런 과정을 반복하며, 구해진 정사각형의 크기(세로변x가로변)중 가장 큰 값을 찾으면 된다.

 

코드

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

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

        int[][] board = new int[N][M];

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


        int maxSize = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 가능한 한 변의 길이 증가시키면서 검사
                for (int k = 1; (i + k < N) && (j + k < M); k++) {
                    // 네 꼭짓점이 같은지 확인
                    if (board[i][j] == board[i + k][j] &&
                            board[i][j] == board[i][j + k] &&
                            board[i][j] == board[i + k][j + k]) {

                        maxSize = Math.max(maxSize, k + 1); // k+1이 실제 변의 길이
                    }
                }
            }
        }

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

 

코드 흐름

1.  입력 받기

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

int[][] board = new int[N][M];

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

• `BufferedReader`와 `StringTokenizer`를 사용하여 N(행)과 M(열) 입력을 받다.
• `board` 2차원 배열을 선언하고, 각 자리의 숫자를 저장한다.
• 숫자는 문자(char)로 주어지므로 '0'을 빼서 정수로 변환한다.

 

2.  정사각형을 찾는 완전 탐색

int maxSize = 1;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        // 가능한 한 변의 길이 증가시키면서 검사
        for (int k = 1; (i + k < N) && (j + k < M); k++) {
            // 네 꼭짓점이 같은지 확인
            if (board[i][j] == board[i + k][j] &&
                board[i][j] == board[i][j + k] &&
                board[i][j] == board[i + k][j + k]) {

                maxSize = Math.max(maxSize, k + 1); // k+1이 실제 변의 길이
            }
        }
    }
}

• `(i, j)`를 왼쪽 위 꼭짓점으로 고정한 후, 가능한 정사각형을 모두 탐색한다.
• 변의 길이를 `k`로 늘려가면서 네 꼭짓점이 같은지 확인한다.
• `maxSize`를 갱신하여 가장 큰 정사각형을 찾는다.