백준 | 1915번. 가장 큰 정사각형 찾기 - DP 문제

🟦 백준 1915번. 가장 큰 정사각형 찾기

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

1915번: 가장 큰 정사각형

문제

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

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

입력

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

출력

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

풀이

• 가장 큰 정사각형 넓이 구하기 == 가장 큰 한 변의 길이 구하기
• 변의 길이 D[i][j]로 점화식 정의

D[i][j] 
//i,j의 위치가 오른쪽 아래 꼭짓점이 되는 부분이라고 했을 때, 
해당 자리에서 그릴 수 있는 가장 큰 정사각형 '한 변의 길이값' 저장

상세 풀이 방식

1) D[][] 배열의 값을 입력된 데이터로 초기화한다.

이떄, 0인 부분은 어차피 그릴 수 없는 부분이므로, 1인 부분에 대해서만 DP를 갱신해줄 것임을 상기시켜라

2) 점화식을 이용하여 DP[][] 배열 값을 다시 갱신해줄 거다.

기존 0 인 부분은 그대로 둔다. 못 그리는 부분

기존 1인 부분은 아래의 조건대로 갱신해줄 거다.

기존 값이 1이면서 i >0, j>0 인 부분에 대하여 

왼쪽 대각선 vs 위 vs 왼쪽 값 중 가장 '작은 값' + 1 

즉, 
if(D[i][j] == 1 && i >0 && j>0){
	D[j][j] = Math.min(D[i-1][j-1] , Math.min(D[i-1][j] , D[i][j-1] ) + D[i][j] ;
 //기존 값을 더하는 이유는 1인 경우이므로 +1 처리 용 
}
if(max  < D[i][j]) max = D[i][j]; 갱신 

3) D[][] 배열에서 가장 큰 값으로 저장한 max 값이 가장 큰 정사각형의 한 변 길이가 된다.

따라서 최종 넓이 답은 ‘(한변)*(한변)’ 이 된다.

---

코드

import java.util.Scanner;

/*1915번. 가장 큰 정사각형 */
public class Main {
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long[][] DP = new long[1001][1001];//가장 max값으로 세팅 
		
		Scanner kb= new Scanner(System.in);
		
		int n = kb.nextInt();
		int m = kb.nextInt();
		
		long max = 0;//최대 변 길이 저장용 
		
		for(int i=0; i<n; i++) {
			//라인 단위로 입력받고 세팅 
			String tmp = kb.next();
			
			for(int j =0; j<m; j++) {
				//라인 단위로 받은 애를 j값으로 하나씩 찍으면서 Long타입으로 변환시킨다음에 저장시켜야 함 
				DP[i][j] = Long.parseLong(String.valueOf(tmp.charAt(j)));
				if(DP[i][j] == 1 && i >0 && j>0 ) {
					DP[i][j] = Math.min(DP[i-1][j-1], Math.min(DP[i-1][j], DP[i][j-1])) + DP[i][j];
				}
				if(max < DP[i][j]) max = DP[i][j];
			}		
		}		
		//최종 넓이 출력 
		System.out.println(max * max);
	}
}