[LeatCode] Medium 221 Maximal Square (Java)

문제 링크

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

문제 설명

이진 행렬(binary matrix)에서 1로만 이루어진 가장 큰 정사각형의 넓이를 찾는 문제

입력

• m x n 크기의 이진 행렬
• 각 셀은 '0' 또는 '1'로 구성

출력

• 1로만 구성된 가장 큰 정사각형의 넓이

예시

입력:

1 1 1
1 1 1
1 1 1

출력: 9 (3x3 정사각형이 가능)

풀이 과정

첫 번째 접근: 슬라이딩 윈도우

1. 가능한 정사각형 크기(1부터 max(m,n)까지)를 순회
2. 각 크기별로 행렬을 순회하면서 윈도우를 이동
3. 각 윈도우 위치에서 모든 원소가 1인지 확인

public int maximalSquare(char[][] matrix) {
    int answer = 0;
    int m = matrix.length;
    int n = matrix[0].length;
    
    for (int length = 1; length <= Math.max(m, n); length++) {
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                if (checkSquare(matrix, x, y, length)) {
                    answer = length * length;
                }
            }
        }
    }
    return answer;
}

첫 번째 접근의 문제점

최악의 경우 시간 초과 (1 <= m, n <= 300)

• 정사각형 크기 순회: O(max(m,n))
• 행렬 순회: O(m x n)
• 각 위치에서 정사각형 확인: O(length^2)
• 총 시간 복잡도: O(max(m,n) x m x n x length^2)

두 번째 접근: 다이나믹 프로그래밍

• 각 위치(i,j)에서 가능한 최대 정사각형의 크기를 계산
• 이전에 계산한 결과를 활용하여 중복 계산 방지

DP 배열의 의미

dp[i][j]: (i,j)를 우하단 꼭지점으로 하는 최대 정사각형의 한 변의 길이

점화식

if matrix[i-1][j-1] == '1':
    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
else:
    dp[i][j] = 0

상세 풀이 과정

초기 설정

int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m + 1][n + 1];
int maxLength = 0;  // 최대 정사각형의 한 변 길이

단계별 진행 예시

예시 매트릭스:

1 1 1
1 1 1
1 1 1

1. 초기 DP 배열 (패딩 포함)

0 0 0 0
0 * * *  (* = 미계산)
0 * * *
0 * * *

2. dp[1][1] 계산 (매트릭스의 [0][0] 위치)

• 위쪽: dp[0][1] = 0
• 왼쪽: dp[1][0] = 0
• 대각선: dp[0][0] = 0
• 현재 위치 값: matrix[0][0] = 1
• 계산: dp[1][1] = min(0,0,0) + 1 = 1

3. 연속된 계산 과정

0 0 0 0    →    0 0 0 0    →    0 0 0 0
0 1 * *         0 1 1 *         0 1 1 1
0 * * *         0 * * *         0 1 2 2
0 * * *         0 * * *         0 1 2 3

시간 복잡도

• O(m x n): 각 셀을 한 번씩만 방문

구현

class Solution {
    public int maximalSquare(char[][] matrix) {

        int answer = 0;

        int m = matrix.length;
        int n = matrix[0].length;

        int[][] dp = new int[m + 1][n + 1];

        int maxLength = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(
                            Math.min(dp[i - 1][j], dp[i][j - 1]),
                            dp[i - 1][j - 1]
                    ) + 1;
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }

        answer = maxLength * maxLength;

        return answer;
    }
}