1915 가장 큰 정사각형

 

입력값을 input 배열에 넣고,

만약 i,j 위치 값이 1일 경우 (아래 그림에서 input[i][j] = 1)

dp[i][j] => dp[i-1][j-1], dp[i-1][j-1], dp[i][j-1] 중 최소값 + 1

하면 된다.

 

 

dp[1][1] = input[0][1], input[0][0], input[1][0] 중 최소값 + 1 하면 되는데,

=> input[0][1] = 1, input[0][0] = 0, input[1][0] = 0 이므로

이 중 최소값은 0 이고

dp[1][1] = 0 + 1 = 1 이 된다.

 

그래서 dp배열을 완성하면 아래와 같다. 

0	1	0	0
0	1	1	1
1	1	2	0
0	0	1	0

 

 

규칙 1

dp를 만들 때, 첫 행, 첫 열은

input행렬의 첫 행, 첫 열 값을 그대로 입력하면 된다.  

 

규칙 2 

dp[i][j] => dp[i-1][j-1], dp[i-1][j-1], dp[i][j-1] 중 최소값 + 1

1) 위 식은, input[i][j] = 1 일 때만 실행하면 된다.

2) input[i][j] = 0 이라면, 그냥 0 그대로 입력하면 된다.

 

 

import java.io.IOException;
import java.util.Scanner;

public class Main {	
	
	public static void main(String[] args) throws IOException {		
	
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int m = s.nextInt();		
		
		int input[][] = new int[n][m];
		
		for(int i=0; i<n; i++) {
			
			String a = s.next();
			
			for(int j=0; j<m; j++) {
				
				input[i][j] =a.charAt(j) - '0';
			}			
		}
		
		
		int dp[][] = new int[n][m];
		int result = 0;
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {						
				
				if(i-1>=0 && j-1>=0 && i-1<n && j-1<m) {
					
					if(input[i][j] !=0 ) {
						
						int min_value1 = Math.min(dp[i-1][j], dp[i-1][j-1]);
						int min_value2 = Math.min(min_value1, dp[i][j-1]);						
						dp[i][j] = min_value2 +1;
						result = Math.max(result, dp[i][j]);					
						
					}			 
				
					// 첫 행, 첫 열 경우
				}else {					
					
					dp[i][j] = input[i][j];
					result = Math.max(result, dp[i][j]);
				}				
				
			}
		}

	
		System.out.println(result*result);
		
		
	}	
}

 

 

 

 

 

 

 

 

 

참고 블로그 : 

https://hy-ung.tistory.com/51

백준 1915번 - 가장 큰 정사각형 (JAVA)