[JAVA] BOJ1915 가장 큰 정사각형

알고리즘 분류

• 다이나믹 프로그래밍

문제 풀이 방법

• 주어진 배열을 arr라고 한다.
• arr[i][j] 원소를 끝 점으로 지정했을 때, 만들 수 있는 정사각형의 최대 길이를 DP[i][j]의 값으로 한다.
  • arr[i][j] == 0 일 때는 정사각형을 만들 수 없으므로, DP[i][j]의 값은 무조건 0이 된다.
• 점화식
  • arr[i][j] == 0, DP[i][j] = 0
  • arr[i][j] == 1, DP[i][j] = Math.min(DP[i - 1][j - 1], Math.min(DP[i][j - 1], DP[i - 1][j]))

코드

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

public class BOJ1915 {
    /*
    가장 큰 정사각형
     */
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n, m, arr[][], dp[][], result;

    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n + 1][m + 1];
        dp = new int[n + 1][m + 1];

        for(int i = 1; i < arr.length; i++) {
            String input = br.readLine();

            for(int j = 1; j < arr[i].length; j++) {
                arr[i][j] = input.charAt(j - 1) - '0';
            }
        }

        for(int i = 1; i < arr.length; i++) {
            for(int j = 1; j< arr[i].length; j++) {
                if(arr[i][j] == 0){
                    dp[i][j] = 0;
                }

                if(arr[i][j] == 1) {
                    int min = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
                    dp[i][j] = min + 1;

                    result = Math.max(result, dp[i][j]);
                }
            }
        }
        System.out.println(result * result);
    }
}

느낀점

• 처음에 DP[i][j]의 값을 arr[i][j]를 끝으로 했을 때, 만들 수 있는 최대 정사각형의 넓이로 지정했다. 이렇게 했을 때 생기는 문제점은 arr[i][j] 값이 0일 때도 DP[i][j]의 값을 구해줘야되고, 맞는 답안 같아도 맞지 않는 경우가 꽤 많았다.
• 처음에 내가 가정 했던 arr[i][j]를 끝으로 했을 때, 만들 수 있는 최대 정사각형의 넓이와 나중에 문제를 풀기 위해 가정했던 arr[i][j]를 끝 점으로 했을 때, 만들 수 있는 정사각형의 한 변의 길이 는 단순히 봤을 때, 비슷한 가정인 것 같아도 문제풀이를 할 때, 확실히 달랐다. DP 문제 풀이를 할 때 문제를 이해하고, 점화식을 올바르게 작성하는 것이 중요하다는 것을 느꼈다.
• 요즘 기업마다 무조건 DP 문제가 한 문제 이상 나오는 것 같아서, DP 문제를 정복하는 것을 목표로 하고 있다. 문제가 풀리지 않을 때, 답안을 보곤 하는데, 내가 너무 어렵게 생각하면서 문제를 더 어렵게 만드는 것 같다. 더 많은 문제를 풀어보면서 DP에 대한 감을 확실히 익혀야 될 것 같다,