[LeetCode] Java - Maximal Square

 

27일차 LeetCode 도전 입니다. 

Maximal Square.

 

1. 문제 

Maximal Square 라는 문제입니다.

1로 구성된 정사각형의 넓이를 구하는 문제입니다.

위의 예제로 보면 1이 4칸으로 구성된 정사각형이고 2 2 이기 때문에 답은 2*2로 4가 출력됩니다.

 

해당 문제는 DP 기본 문제로 생각보다 쉽게 구현이 가능합니다.

 

2. 풀이

class Solution {
    public int maximalSquare(char[][] matrix) {
        
    	int n = matrix.length;
        if(n == 0) return 0;
    	int m = matrix[0].length;
    	
    	int[][] DP = new int[n+1][m+1];
    	int max = 0;
    	
    	for(int i=1; i<=n; i++) {
    		for(int j=1; j<m+1; j++) {
    			if(matrix[i-1][j-1] == '1') {
    				DP[i][j] = Math.min(DP[i-1][j], Math.min(DP[i][j-1], DP[i-1][j-1]))+1;
    			}
    			max = Math.max(DP[i][j], max);
    		}
    	}
    	
        return max * max;
    }
}

DP 식을 만들면 아래와 같이 만들 수 있습니다.

 

DP = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) ( if matrix[i][j] == '1' )

 

대각선, 위, 옆 칸을 보고 제일 작은 값의 +1을 하면 최대 네모칸을 확인 할 수 있습니다.

그래서 위와 같이 코드를 작성하면 통과 가능 합니다.