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

1. 문제

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

• DP 문제

// 문제
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개의 숫자로 배열이 주어진다.

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

// 예제 입력 1
4 4
0100
0111
1110
0010

// 예제 출력 1
4

2. 핵심 아이디어

• DP로 구현

3. Python 문제풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [[0 for _ in range(m + 1)] for i in range(n + 1)]
# dp[i][j] = i, j까지 왔을 때, 가장 큰 정사각형의 한 변의 길이
# dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1
dp = [[0 for _ in range(m + 1)] for i in range(n + 1)]

for i in range(n) :
  for idx, j in enumerate(list(map(int, list(input().rstrip())))) :
    arr[i + 1][idx + 1] = j

for i in range(1, n + 1) :
  for j in range(1, m + 1) :
    if arr[i][j] :
      dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1

print(max([max(i) for i in dp]) ** 2)

4. Java 문제풀이

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

class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int[][] dp = new int[1001][1001];
    int ans = 0;
    for(int i = 0; i < n; i ++){
      char[] line = br.readLine().toCharArray();
      for(int j = 0; j < line.length; j++){
        dp[i + 1][j + 1] = line[j] - '0';
        if(dp[i + 1][j + 1] != 0){
          int temp = Math.min(dp[i][j], dp[i][j + 1]);
          dp[i + 1][j + 1] = Math.min(temp, dp[i + 1][j]) + 1;
          ans = Math.max(ans, dp[i + 1][j + 1]);
        }
      }
    }
    bw.write((ans * ans) + "\n");

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