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

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

1915번: 가장 큰 정사각형

🔶 풀이

처음에 완전 탐색으로 풀어보려했지만 n과 m의 범위를 보고 바로 후퇴...

어떻게 풀어야할지 감이 안잡혀서 [알고리즘 분류]를 봤더니 다이나믹 프로그래밍이였다.

 

dp 알고리즘의 기본은 점화식을 찾아야된다.

점화식을 찾는건 정말 힘들다. 소소한 팁을 주자면 공책에 적어보면 규칙이 보인다.

 

가장 큰 정사각형의 넓이를 구해야한다.

우선, N=1 혹은 M=1인 상황은 무조건 1을 출력한다. (문제에서 배열의 크기는 1부터 1000이라고 명시되어있음)

 

2x2 이상의 크기를 가진 배열부터 규칙이 생긴다.

특정 칸에 대해서 주변 3개의 칸이 모두 1을 가지고 있어야 정사각형이 된다.

 

위 그림은 3x3 배열의 값이 모두 1이라고 가정했을 때 dp 배열이 어떻게 되는지를 보여준다.

 

우측 하단 칸을 기준으로 점화식을 세웠다.

우측 하단 칸의 좌표가 (x, y) 라고 한다면 (x-1, y), (x-1, y-1), (x, y-1)의 칸이 모두 1을 가지고 있으면 정사각형이 되고, 하나라도 0이 있다면 정사각형이 될 수 없다.

 

따라서, 3개의 칸 중에서 가장 작은 값을 뽑아서 1을 더해주면서 (n, m) 까지 진행해주면 된다.

if (tmp == 1) {
    dp[i][j] = Math.min(dp[i][j-1], Math.min(dp[i-1][j], dp[i-1][j-1])) +1;
    ans = Math.max(ans, dp[i][j]);
}

dp[i][j]를 구해줬다면 현재 가장 큰 값을 ans 변수에 넣고, 마지막에 ans*ans를 해주면 가장 큰 정사각형의 넓이를 구할 수 있다.

 

<최종코드>

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

public class Main {
    public static void main(String[] args) throws IOException {
        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());
        
        if (N == 1 || M == 1) {
            System.out.println(1);
            return;
        }
        
        int[][] dp = new int[N+1][M+1];
        int ans = 0;
		
        for (int i=1; i<N+1; i++) {
            String str = br.readLine();
            for (int j=1; j<M+1; j++) {
                int tmp = str.charAt(j-1) - '0';
				
                if (tmp == 1) {
                    dp[i][j] = Math.min(dp[i][j-1], Math.min(dp[i-1][j], dp[i-1][j-1])) +1;
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        }
		
        System.out.println(ans*ans);
    }
}