[BaekJoon] 1915 가장 큰 정사각형 (Java)

1.  문제 링크

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

2.  문제

요약

• n x m의 0, 1로 된 배열이 있습니다.
• 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 n, m이 주어지고 두 번째 줄부터 n개의 줄에는 m개의 숫자로 배열이 주어집니다.
• 출력: 첫 번째 줄에 가장 큰 정사각형의 넓이를 출력합니다.

3.  소스코드

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

public class Main {
	static int n, m, result;
	static int[][] matrix, dp;
	static void input() {
		Reader scanner = new Reader();
		n = scanner.nextInt();
		m = scanner.nextInt();
		matrix = new int[n][m];
		dp = new int[n][m];
		result = 0;
		for(int row = 0; row < n; row++) {
			String info = scanner.nextLine();
			for(int col = 0; col < m; col++) {
				matrix[row][col] = info.charAt(col) - '0';
				dp[row][col] = matrix[row][col];
				if(dp[row][col] == 1) result = 1;
			}
		}
	}
	
	static void solution() {
		for(int row = 1; row < n; row++) {
			for(int col = 1; col < m; col++) {
				if(matrix[row][col] == 1) {
					dp[row][col] = Math.min(dp[row][col - 1], Math.min(dp[row - 1][col], dp[row - 1][col - 1])) + 1;
					result = dp[row][col] > result ? dp[row][col] : result;
				}
			}
		}
		System.out.println(result * result);
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}