1915 : 가장 큰 정사각형

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

 

알고리즘 분류 : 다이나믹프로그래밍

---

문제

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

출력

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

---

접근

• map[i][j]이 1일 때, map[i-1][j], map[i][j-1], map[i-1][j-1]이 모두 1이면, 정사각형을 이룬다. 
• 처음에는 if문을 이용하여 1인지 아닌지 비교하여 풀이하였다. 
• 구글링을 통해, math.min을 이용하여 풀이하면 더욱 깔끔해서 풀이를 수정하였다. 

입력 값

출력 값

 

• 2의 의미는 변의 길이가 2라고 생각하면 된다. 따라서 결과값인 최대 넓이는 2 x 2 = 4 가 된다. 

---

코드

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));
        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[][] map = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            char[] c = br.readLine().toCharArray();
            int k = 0;
            for (int j = 1; j <= m; j++) {
                map[i][j] = c[k] - 48;
                k++;
            }
        }
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (map[i][j] == 1) {
                    map[i][j] = Math.min(Math.min(map[i][j - 1], map[i - 1][j]), map[i - 1][j - 1]) + 1;
                }
            }
        }
 
        int max = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (max < map[i][j])
                    max = map[i][j];
            }
        }
 
        System.out.println(max * max);
 
        bw.flush();
        br.close();
    }
}