[Gold IV] 가장 큰 정사각형 - 1915

문제 링크

성능 요약

메모리: 31372 KB, 시간: 364 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 5월 27일 21:30:36

문제 설명

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

풀이

핵심 아이디어 : dp[i][j]를 "(i,j)를 우하단 꼭짓점으로 하는 가장 큰 정사각형의 한 변의 길이"로 정의하는 것.

점화식:

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1  (board[i][j] == 1일 때)
dp[i][j] = 0  (board[i][j] == 0일 때)

1. 첫 번째 행과 열은 기본값으로 초기화 (1이면 1, 0이면 0)
2. (1,1)부터 시작해서 현재 위치가 1이면, 왼쪽, 위쪽, 대각선 위쪽의 dp 값 중 최솟값에 1을 더함.
3. 정사각형을 만들기 위해 세 방향 모두에서 최소 크기만큼만 확장 가능하기 때문.
4. 최대 dp 값을 제곱하면 최대 정사각형의 넓이.

• 시간복잡도: $O(N×M)$

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int board[][], dp[][];
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_1915_가장큰정사각형/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        for(int i=0; i<n; i++){
            String line = br.readLine();
            for(int j=0; j<m; j++){
                board[i][j] = line.charAt(j) - '0';
            }
        }

        dp = new int[n][m];
        if(board[0][0] == 1) dp[0][0] = 1;
        for(int i=1; i<n; i++){
            if(board[i][0] == 1) dp[i][0] = 1;
        }
        for(int j=1; j<m; j++){
            if(board[0][j] == 1) dp[0][j] = 1;
        }

        boolean flag = false;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == 1) {
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }
        if(!flag) {
            System.out.println(0);
            return;
        }

        int max = 1;
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(board[i][j] == 1) {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j])) + 1;
                    max = Math.max(max, dp[i][j]);
                }
                else{
                    dp[i][j] = 0;
                }
            }
        }
//        for(int i = 0; i < n; i++) {
//            System.out.println(Arrays.toString(dp[i]));
//        }
        System.out.println(max * max);

        bw.flush();
        bw.close();
        br.close();
    }
}