백준 1915 가장 큰 정사각형 (Java)

1. 문제 링크

1915번: 가장 큰 정사각형

 

2. 문제 및 입출력예제

 

3. 문제 풀이

예전에 올렸던 목장 건설하기와 거의 같은 문제이다.

1. 0은 true로, 1은 false로 저장한다.
2. 0이 나오면 해당위치에서 (-1, 0), (-1, -1), (0, -1)의 dp 중 최솟값을 선택하고 1을 더한 값으로 저장한다.
   2-1. 세 좌표는 정사각형의 각 모서리로 포함되는 위치들이다.
   2-2. 그 중 제일 작은 값만큼만 만들 수 있고, 지금 자리도 포함할 수 있으니까 1을 더한다.
3. 좌표에서 dp를 구할 때마다 최댓값을 갱신한다.

 

4. 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int N = Integer.parseInt(split[0]);
		int M = Integer.parseInt(split[1]);
		boolean[][] map = new boolean[N+1][M+1];
		
		for(int i=1;i<N+1;i++) {
			String str = br.readLine();
			for(int j=1;j<M+1;j++) {
				if(str.charAt(j-1) == '1') {
					map[i][j] = true;
				}
			}
		}
        
		int[][] dp = new int[N+1][M+1];
		int max = 0;
		for(int i=1;i<N+1;i++) {
			for(int j=1;j<M+1;j++) {
				if(map[i][j]) {
					dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1;
					max = Math.max(max, dp[i][j]);
				}
			}
		}
		System.out.println(max * max);
	}

}