[백준 문제 풀기] 1915번: 가장 큰 정사각형 (DP, 자바)

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

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

 

예제 입력, 출력

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

 

사용 알고리즘

DP

 

코드 (자바)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/1915
// 가장 큰 정사각형

// 참고한 설명 : http://melonicedlatte.com/algorithm/2018/07/15/224137.html


public class Main {
	
	static int min (int a, int b) {
		return (a>b) ? b : a ;
	}
	
	static int max (int a, int b) {
		return (a<b) ? b : a ;
	}
	

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int map[][] = new int[n+1][m+1];
		int dp[][] = new int[n+1][m+1];		// n, m 을 오른쪽 아래점으로 하는 정사각형의 한변의 길이를 저장
		
		for (int i=1 ; i<=n ; i++) {
			String temp = br.readLine().trim();
			for (int j=1 ; j<=m ; j++) {
				map[i][j] = temp.charAt(j-1) - '0' ;	// char 가 아스키 코드를 int 로 저장하기 때문에 숫자로 변환하기 위해서 '0' 을 빼줌
				
			}
		}

//		System.out.println(Arrays.deepToString(map));
		
		// 로직 시작		
		int maxVal = 0;		// 가장 긴 길이를 저장할 변수
		for (int i=1 ; i<=n ; i++) {
			for (int j=1 ; j<=m ; j++) {
				if (map[i][j] == 1) {		// 현재 점이 0 일 경우 연산할 필요 없음
					dp[i][j] = min (dp[i-1][j-1] , min (dp[i-1][j], dp[i][j-1]) ) + 1 ;
					maxVal = max(maxVal, dp[i][j]); 
				}				
			}		
		}
		
		System.out.println(maxVal * maxVal); 		// maxVal 은 한변의 길이이므로 정사각형의 넓이는 제곱을 출력
		
	}
}

/* [인터돌™] 공부 해보자!! 열심히~~~ http://globalhost.tistory.com */