(Java) 백준 1051번 - 숫자 정사각형

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

문제

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

접근

정사각형은 네 변의 길이가 같은 사각형이다. 따라서 주어진 숫자 직사각형을 각 행마다 동일한 숫자가 있는지 확인하며 있다면 두 좌표의 차이를 한 변의 길이로 잡고 해당 길이 만큼 행을 이동해 남은 두 꼭짓점을 잡는다. 해당 두 꼭짓점의 숫자또한 동일하다면 앞서 구한 길이의 제곱으로 정사각형의 넓이를 구한다.
이 넓이들 중 가장 큰 넓이를 출력한다.

문제해결

> 행을 N, 열을 M으로, 숫자 직사각형의 각 숫자를 저장할 이차원 배열을 square로, 최대 크기를 저장할 변수를 rst로 선언한다.
> 정사각형은 적어도 1의 크기를 가지므로 rst의 초기값을 1로 잡는다.
> 주어진 숫자 직사각형의 숫자를 하나씩 잘라 이차원배열에 넣어 좌표화 한다.
> 행이나 열중 하나라도 1이라면 반드시 정사각형이 1의 크기만 가능하므로 rst를 그대로 반환하고 끝낸다.
> 각 행마다 열을 하나씩 잡고 잡은 열 이후에 있는 열들을 각각 비교해본다.
> 두 값이 같다면 일단 열의 차이로 정사각형의 한 변의 길이 dist를 구한다.
> 해당 길이를 현 행값에 더해 남은 두 꼭짓점의 좌표를 잡는다.
> 이때 새로운 행이 N보다 크면 불가능하므로 이를 제외하고 아닐 경우 새로운 두 꼭짓점도 같은 숫자를 가지는지 확인한다.
> 같은 값을 가지면 dist+1의 제곱으로 사각형의 넓이를 구해 rst와 최대값 연산으로 가장 큰 값을 찾아준다.

코드

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

public class Main {
    //1051번 숫자 정사각형
    static int N,M;
    static int[][] square;
    static int rst = 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());
        square = new int[N][M];

        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';
        }

        if(N == 1 || M == 1) {
            System.out.print(rst);
            System.exit(0);
        }

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                for(int t = j; t < M; t++) {
                    if(j == t) continue;
                    if(square[i][j] != square[i][t]) continue;
                    int dist = t - j;
                    int ni = i + dist;
                    if(ni >= N) continue;
                    if(square[i][j] == square[ni][j] && square[i][j] == square[ni][t]) {
                        rst = Math.max(rst, (dist+1) * (dist + 1));
                    }
                }
            }
        }
        System.out.print(rst);
    }
}

후기

오랜만에 푸는 자바문제라 헷갈리는 문법이 많았다.
다시 열심히 해보자