가장 큰 정사각형

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

1915번: 가장 큰 정사각형

문제 설명

2차원 배열을 알려 주면 칸에 숫자가 1인 제일큰 정사각형의 넓이를 찾으면 된다.

 

문제에 대한 이이디어

이런 문제들은 점화식을 잘 찾아서 사용해야 한다. 그래서 더 어려운 것 같다.

정사각형의 넓이를 찾아라를 쉽게 말하면 정사각형이 될 수 있는 한 변의 최대 길이를 찾아라 라고 할 수 있다.

 

어떻게 정사각형의 한 변의 길이를 찾을 수 있을까? 

정사각형의 조건은 가로 세로의 길이가 같고 또 모든 인접한 면이 1이어야 한다.

• 지금 자신이 1이라면
• 왼쪽 대각선 위, 바로 위, 왼쪽이 모두 1일경우 정사각형을 만들 수 있다.
• 각 3개의 방향에서 최솟값을 찾는다.
• 지금 자신의 숫자를 더해준다.

지금 3,3 지점에 1이 들어와야 할 차례이다. 

화살표 방향으로 검사해 그 중 최솟값을 찾는다. 여기서는 최솟값이 1이다. 최솟값에 지금 자신의 값(1)을 더한다.

 이렇게 변하고 지금 만들 수 있는 정사각형의 한 변의 크기는 최대 2이다.

 

구현

import java.io.IOException;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long pro[][] = new long[n][m];
        long max =0;
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            for (int j = 0; j < m; j++) {
                pro[i][j] = Long.parseLong(String.valueOf(str.charAt(j)));
                if(pro[i][j] == 1 && i > 0 && j > 0){
                    pro[i][j] = Math.min(pro[i-1][j-1], Math.min(pro[i-1][j], pro[i][j-1])) + pro[i][j];
                }
                max = Math.max(pro[i][j], max);
            }
        }
        System.out.println(max * max);
    }
}

DP는 맨날 코드는 짧지만 생각하기가 어렵다 ㅜㅜ

 

 

https://github.com/Heron-Woong/CodingTest_Practice/commit/3c0ba9c3bfc50d3e441837ffa2f1fb9549ea6367

백준_1915, 가장 큰 정사각형 · Heron-Woong/CodingTest_Practice@3c0ba9c