[백준 - 1915번] 가장 큰 정사각형 - Java //Wello Horld//

이번에는 BOJ의 1915번 문제 "가장 큰 정사각형"을 풀어보도록 하자

다이나믹 프로그래밍으로 풀면 간단하게 풀리는 문제이다. 입력으로 먼저 n, m 주어지고, 그 다음 n개의 줄에 m개 만큼 "0"이나 "1"이 주어진다. 이것을 이용해서, 1로 이루어져 있는 가장 큰 정사각형의 넓이를 구하면 되는 문제이다. 예제를 보면

• 4 4
• 0100
• 0111
• 1110
• 0010

이 주어졌을 때, 가운데에 있는 굵은 글씨부분이 가장 큰 정사각형이고, 그 넓이는 4가 된다.

이것을 풀 때, 입력을 배열로 받으면서 계산까지 가능하도록 프로그램을 만들어서, 살짝 더럽긴하지만, 성공한 코드는 아래와같다. 

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

public class sample {
    public static void main(String[] args) throws Exception {
        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][10001];
        int ans = 0;
        for(int i = 0; i < n; i ++){
            char[] line = br.readLine().toCharArray();
            for(int j = 0; j < line.length; j++){
                //dp의 0행, 0열 -> 모두 '0'으로 만들어주기 위해 dp[i+1][j+1] 로 해줌
                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();
    }
}

 

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

1915번: 가장 큰 정사각형