[백준/boj] 1915: 가장 큰 정사각형 (Java) / DP

문제

1915번: 가장 큰 정사각형

풀이

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

public class Main_BOJ_1915_가장큰정사각형 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M, maxNum = 0;
	static char[][] map;
	static int[][] dp;

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		dp = new int[N][M];
		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
			for (int j = 0; j < M; j++) {
				dp[i][j] = map[i][j] - '0';
				if(dp[i][j] == 1 && maxNum == 0) maxNum =1;
				if (j > 0 && i > 0) {
					if (dp[i - 1][j] > 0 && dp[i][j - 1] > 0 && dp[i - 1][j - 1] > 0 && dp[i][j] == 1) {
						dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
						maxNum = Math.max(dp[i][j], maxNum);
					}
				}
			}
		}
		System.out.println(maxNum* maxNum);
	}
}

첫번째 행부터 받아오면서 

dp 배열, 기준: 박스

이런 네모 상태에서 2행 2열을 기준으로 나머지 셋이 0보다 크고 (사각형을 구성할 조건을 갖춤), 2행 2열인 내가 1이라면 나머지 셋중 가장 작은 값에 +1 을 한 값을 dp 배열에 저장한다. 위와 같은 경우에는 조건에 맞지 않아 그냥 dp에 map의 값인 1을 할당하고 넘어간다.

dp 배열

이러한 경우엔 2가 저장된다. 

그럼 3x3 크기의 정사각형이라면 어떻게 될까?

주황박스 좌표를 받아올 때 dp 배열은 왼쪽과 같은 상태일 것이다. 이때, 셋 중 가장 작은 값인 2 에 1을 더한 값인 3이 저장된다.