[백준] 1915 가장 큰 정사각형 - DP JAVA

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

1915번: 가장 큰 정사각형

코드설명

DP 문제입니다.

 

이 문제같은경우, 시작지점에서 검사하는것이 아닌 도착지점에서 좌측, 우측, 좌상대각측을 살펴보면서 진행해야합니다.

DP[N+1][M+1] 에서 DP 배열의 역할은, N+1과 M+1 위치에서 가능한 정사각형의 크기를 의미합니다.

문제에서 주어진 예제의 DP 값입니다.

입력
4 4
0100
0111
1110
0010
 
DP 저장
0 1 0 0
0 1 1 1
1 1 2 0
0 0 1 0

만약 arr[i][j] == 1 이라면, 해당 3가지 방향에서 가장 작은 값에 + 1 을 합니다.

만약 DP[i-1][j], DP[i][j-1], DP[i-1][j-1] 3가지 방향 모두 1 1 1 이라면, 해당 DP[i][j] = 2 가 되면서 최대 정사각형 배열의 길이는 2가 됩니다.

 

위의 로직을 통해 해결할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M;
	public static int[][] arr;
	public static int[][] dp;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	arr = new int[N+1][M+1];
    	dp = new int[N+1][M+1];
    	
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		String str = st.nextToken();
    		for(int j=1;j<=M;j++) {
    			arr[i][j] = str.charAt(j-1) - '0';
    		}
    	}
    	if(N==1 && M == 1 && arr[1][1] == 1) {
    		System.out.println(1);
    		return ;
    	}else if(N==1 && M == 1 && arr[1][1] == 0){
    		System.out.println(0);
    		return ;
    	}
    	
    	int[][] dp = new int[N+1][M+1];
    	for(int i=1;i<=N;i++) {
    		
    		for(int j=1;j<=M;j++) {
    			if(i == 1 && j == 1) {
    				dp[i][j] = arr[i][j]; //첫 (1,1) 지점은 좌 방향, 좌상대각 방향, 우측방향 이 없습니다. 
    			}else {
    				if(arr[i][j] == 1) {
    					dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1; //만약 3가지 방향중에 하나라도 0 이라면 dp[i][j] 도 0이되면서 불가능하다.
        				answer = Math.max(answer,  dp[i][j]);	
    				}
    				
    			}
    		}
    	}
    	System.out.println(answer * answer);
    	
    	
	}
}