[백준] 숫자 정사각형

알고리즘

[백준] 숫자 정사각형 - Java

BGK97 2025. 1. 26. 15:08

문제 출처

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

문제

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

입력

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

출력

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

예제 입력 1

예제 출력 1

예제 입력 2

2 2
12
34

예제 출력 2

예제 입력 3

2 4
1255
3455

예제 출력 3

예제 입력 4

1 10
1234567890

예제 출력 4

예제 입력 5

예제 출력 5

풀이 방법

범위가 N과 M의 50이내고, 제한시간이 2초였기 때문에 좀 여유로운 시간이었다.
배열을 완전탐색하면서, N과 M중 더 작은 부분을 맥시멈 비교값으로 설정하여 추가 탐색을 진행하여, 정사각형 모서리의 값들이 같은 경우 넓이를 치환해주었다.

풀이 코드

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

public class Main {
    static int N, M, num;
    static int[][] square;

    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());
        square = new int[N][M];

        // 비교 대상 정하기(더 큰거하면 idx넘어가므로)
        num = N > M ? M : N;

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

        // 최소 넓이 1
        int maxArea = 1;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                for (int k = 1; k < num; k++) {
                    if (checkSquare(i, j, k)) {
                        maxArea = Math.max(maxArea, (int)(Math.pow(k + 1, 2)));
                    }
                }
            }
        }

        System.out.println(maxArea);
    }

    public static boolean checkSquare(int i, int j, int k) {
        //범위 내이며, 같은 숫자를 가진 정사각형이라면
        if (i + k < N && j + k < M && square[i][j] == square[i + k][j] && square[i][j] == square[i][j + k]
                && square[i][j] == square[i + k][j + k]) {
                    return true;
            }
        return false;
    }
}

결과

회고

if 값에 먼저 maxArea를 비교해주면 시간이 줄지않을까 했지만, 비슷했다. 어짜피 검사하니까 O(1)이 사용되어서 그런것인가...?

저작자표시 비영리 동일조건