[백준] 1915번 : 가장 큰 정사각형

문제

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

문제해결방법

이 문제는 DP 문제로 점화식을 세워서 푸는 문제였다.

좌측 상단부터 우측 하단까지 배열을 탐색하며 해당 칸을 우측 하단으로 하는 가장 큰 정사각형의 크기를 기록한다.

예를 들어 위 그림은 배열의 값이 1인 (i, j) 칸을 탐색하는 중 (i-1, j) 칸에 5, (i-1, j-1) 칸에 6, (i, j-1) 칸에 3이 저장되어 있는 상태이다.

이때 셋 중에 가장 작은 값인 3을 선택해야 길이가 4인 가장 큰 정사각형을 만들 수 있다. (회색 점선)

위 내용을 점화식으로 표현하면 다음과 같다.

DP[i][j] = Min(DP[i-1][j-1], DP[i-1][j], DP[i][j-1]) + 1

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main1915_가장큰정사각형 {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] dp = new int[n+2][m+2];
        int max = 0;
        for(int i=1; i<=n; i++) {
            String s = br.readLine();
            for(int j=1; j<=m; j++) {
                dp[i][j] = s.charAt(j-1)-'0';
                if(dp[i][j]==1) {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j]))+1;
                    if(max < dp[i][j]) max = dp[i][j];
                }
            }
        }
        System.out.println(max*max);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.