백준 1051 숫자 정사각형

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

public class Number_Rectangle {
    static int N;
    static int M;
    static int answer=0;
    static char[][] map;
    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());
        map = new char[N][M];

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
            }
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                search(i,j);
                max = Math.max(max,answer);
            }
        }
        System.out.println(max);
    }
    public static void search(int row, int col){
        List<Integer> list = new ArrayList<>();
        for (int i = 0; col+i < M; i++) {
            if(map[row][col+i]==map[row][col]){
                list.add(i);
            }
        }
        if(list.isEmpty()){
            return;
        }

        for (int i = list.size()-1; i >=0; i--) {
            if(N<=row+list.get(i))
                continue;
            if(map[row+list.get(i)][col]==map[row][col] && map[row+list.get(i)][col+list.get(i)]==map[row][col]){
                answer = (list.get(i)+1)*(list.get(i)+1);
                return;
            }
        }
    }
}

풀이방법

1. 맵 전체를 완전탐색 하여 search함수로 좌표를 넘겨준다.
2. 넘겨준 좌표에서 오른쪽 방향으로 탐색하며 같은 수의 꼭지점을 가진 좌표를 찾고, 거기까지의 거리를 list에 넣는다.
3. 같은 수의 꼭지점이 없다면 search 함수를 빠져나간다.
4. y축에서 list의 마지막에 담긴 거리(가장 큰 정사각형의 변)만큼 떨어진 좌표, x,y에서 떨어진 좌표를 확인해서 모두 같은 수라면 그때의 거리를 곱해 사각형의 넓이를 구한다.