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

BOJ 1915 가장 큰 정사각형

문제풀이

다차원 다이나믹프로그래밍으로 풀이가 가능한 문제였다.

• dp[i][j]는 현재 [i][j]칸을 정사각형의 가장 오른쪽 아래로 했을 때 만들 수 있는 가장 큰 정사각형의 한 변의 길이다.
• dp[i][j]는 map[i][j]가 1일 때만 갱신한다.
• dp[i][j]는 dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1] 중 가장 작은 값 + 1이다.

구현코드

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

public class Main {

	static int map[][];
	static int dp[][];
	static int N, M, ans;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		
		ans = 0;
		map = new int[N][M];
		dp = new int[N][M];
		
		for(int i = 0 ; i < N ; ++i) {
			char[] line = br.readLine().toCharArray();
			for(int j = 0 ; j < M ; ++j) {
				map[i][j] = line[j] - '0';
				dp[i][j] = line[j] - '0';
				if(dp[i][j] == 1) ans = 1;
			}
		}
		
		for(int i = 1 ; i < N ; ++i) {
			for(int j = 1 ; j < M ; ++j) {
				if(map[i][j] == 1) {
					dp[i][j] = Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1])) + 1; 
					ans = dp[i][j] > ans ? dp[i][j] : ans;
				}
			}
		}
		
		System.out.println(ans * ans);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}