Maximal Square(Array,Dynamic Programming,Matrix)

https://leetcode.com/problems/maximal-square/description/

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is '0' or '1'.

으.. 넘 짜증나는 Dynamic programming, 심지어 Matrix 문제다.

 

1. Python

아 진짜 DP를 어떻게 써야할 지 몰라서 Naive하게 풀었는데,

간단한 test case는 다 OK 되지만 또 역시나 Time limit에 걸렸다. 나으 코드는 아래와 같다..

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # dp를 어떻게 적용할 지는 모르겠다.
        m = len(matrix)
        n = len(matrix[0])
        ans = 0
        # 좌표 (i,j,cnt->처음 시작 1)를 집어넣다.
        def square(i:int,j:int,cnt:int) -> int :
            # 정사각형이 틀을 벗어나는 경우
            if i+cnt > n-1 or j+cnt > m-1  or matrix[j][i+cnt]=="0" : return cnt*cnt

            for p in range(1,cnt+1):
                if matrix[j+p][i+cnt] == "0":
                    return cnt*cnt

            for q in range(1,cnt+1):
                if matrix[j+cnt][i+cnt-q] == "0":
                    return cnt*cnt

            return square(i,j,cnt+1)
    
        # for 전체를 돌며 1인 놈만 체크해서 아래부분을 훑는 Square search method를 실행한다.
        for i in range(n):
            for j in range(m):
                if matrix[j][i] == "1":
                    ans = max(ans,square(i,j,1))

        return ans

거지같넹

 

역시나 시간효율 개선을 위해선 DP를 써야한다.

DP를 과연 어떻게 쓸 것인가.. 아래를 참고해보자

 

DP 코드를 첨 보았을땐, 이게 뭔가.. 했는데 코드를 볼수록 Ah- moment가 찾아왔다. 분명 효율적이긴 한데, 솔직히 처음부터 내가 이걸 바로 생각해냈으리라는 기대는 들지 않는다. 그만큼 아직 훈련이 많이 필요하다는 것이다ㅠㅠ

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        n = len(matrix[0])

        # Using DP! initialize
        dp = [[0] * n for _ in range(m)] # 현재 위치에서 만들 수 있는 최대 정사각형의 길이
        ans = 0

        # Do DP for each cell
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    if i==0 or j==0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 # why?
                ans = max(ans,dp[i][j])
        return ans*ans

 

2. C++로도 DP풀어보기

특이점은, Matrix를 C++에서 0으로 초기화 해줄 때 아래와 같이 한다.

m*n matrix라고 했을때,

vector<vector<int>> dp(m,vector<int>(n,0)) --> 신기하당

 

그리고 min/max는 python에선 여러개 비교 되었는데 C++에선 2개만 된다. 그래서 3개 비교할땐 그냥 아래처럼 2번 min/max를 써주자.

 

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        vector<vector<int>> dp(m,vector<int>(n,0)); // 초기화 하는 법 숙지
        int ans = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                    if(i==0 || j==0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    }
                }
                ans = max(ans,dp[i][j]);
            }
        }
        return ans*ans;
    }
};

 

3. C

C는 좀 귀찮은데 이중 Matrix다 보니까 (int**) 형태로 Malloc을 두 번씩 써주면 된다.

#include <stdio.h>
#include <stdlib.h>

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize) {
    if (matrixSize == 0 || matrixColSize[0] == 0) return 0;

    int m = matrixSize;
    int n = matrixColSize[0];
    int maxSide = 0;

    // dp 배열 동적 할당 및 초기화
    int** dp = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        dp[i] = (int*)malloc(n * sizeof(int));
    }

    // DP를 통해 최대 정사각형 한 변의 길이를 계산
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                if (i == 0 || j == 0) {
                    // 첫 행이나 첫 열의 경우, 그냥 1로 설정
                    dp[i][j] = 1;
                } else {
                    // 위, 왼쪽, 대각선 위-왼쪽의 최소값 + 1
                    dp[i][j] = (dp[i - 1][j] < dp[i][j - 1] ? (dp[i - 1][j] < dp[i - 1][j - 1] ? dp[i - 1][j] : dp[i - 1][j - 1]) : (dp[i][j - 1] < dp[i - 1][j - 1] ? dp[i][j - 1] : dp[i - 1][j - 1])) + 1;
                }
                if (dp[i][j] > maxSide) maxSide = dp[i][j];
            } else {
                dp[i][j] = 0;
            }
        }
    }

    // 메모리 해제
    for (int i = 0; i < m; i++) {
        free(dp[i]);
    }
    free(dp);

    // 정사각형의 넓이 반환
    return maxSide * maxSide;
}

int main() {
    // 예제 입력 (1은 '1'로, 0은 '0'으로 입력)
    char* matrix[] = {
        "10100",
        "10111",
        "11111",
        "10010"
    };
    int matrixSize = 4;
    int matrixColSize[] = {5, 5, 5, 5};

    int result = maximalSquare(matrix, matrixSize, matrixColSize);
    printf("The area of the largest square is: %d\n", result);

    return 0;
}