[Leetcode] 221. Maximal Square

문제 요약

• 알고리즘 분류: DP
• 난이도: Medium
• 문제내용:
  • 가로, 세로 안에 0 과 1로 채워져 있다. 0은 빈곳 1은 면적이 있는 공간이다.
  • 정사각형 최대 넓이를 구하여라
• 사이트 주소: https://leetcode.com/problems/maximal-square/description/

문제풀이 

 이번 문제는 간단한 DP(동적계획법) 문제이다. DP에 대한 자세한 설명은 아래글에서 확인 해보면 된다.

https://jih3508.tistory.com/89

[알고리즘 이론] 동적계획법(Dynamic Programming, DP)

문제 접근방법

DP(Dynamic Programming) 문제의 해결은 주로 구현보다는 문제 해결에 필요한 아이디어를 요구합니다. DP 알고리즘에서 가장 중요한 부분은 점화식의 세우는 것인데, 이는 다음과 같이 간단하게 할 수 있습니다.

1. 기본 설정: 0번째 행과 열을 그대로 유지한 채로, (1, 1) 위치부터 계산을 시작합니다.

2. 값 계산: 각 위치에서 0일 때와 1일 때를 나누어 계산을 진행합니다.

• 0인 경우: 현재 위치의 DP 값은 0으로 설정합니다.
• 1인 경우: 왼쪽, 위쪽, 왼쪽 대각선 위의 세 값 중 최소값을 찾아서 거기에 1을 더해 현재 위치의 DP 값을 설정합니다.

3. 이유: 정사각형의 기준은 가로와 세로의 길이가 같아야 합니다. 하지만 현재 위치에서 위, 왼쪽, 대각선 위 중 하나라도 다르면 정사각형이 될 수 없습니다. 따라서 이전에 저장한 값들 중 최소값에 1을 더함으로써 정사각형의 최대 면적을 표시할 수 있습니다.

따라서 점화식은 아래 같이 세울수 있다.

점화식

위의 설명을 그림으로 보면 더 쉽게 이해될 것입니다.

 초록색 부분과 화살표 부분만 보면 초록색 칠한 부분에서는 왼쪽, 위 , 대각선 쪽합하면 정사각형 구조가 나온다. 그래서 이전 저장한 쪽중 가장 작은 값 + 1하면 끝이다. 그리고 마직막으로 제곱해서 return 해주는것을 잊지 말자

위와 같이 풀면 가로, 세로 사각형 면적 만큼 탐색 하면 되기 때문에 시간 복잡도는 O(N ^ 2)만큼 나온다.

Code

Python

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # 초기 설정
        # 가로, 세로 높이
        width, height = len(matrix[0]), len(matrix)
        
        # 최대값
        maxValue = 0

        # dp 초기화
        dp = [[0] * width for _ in range(height)]

        # 각 행렬 0번 째 인덱스 초기화
        for i in range(width):
            dp[0][i] = int(matrix[0][i])
            maxValue = max(maxValue, dp[0][i])

        for i in range(height):
            dp[i][0] = int(matrix[i][0])
            maxValue = max(maxValue, dp[i][0])

        # (1, 1)위치 부터 탐색
        for x in range(1, height):
            for y in range(1, width):
                # 현재 위치가 1일 경우 왼쪽, 위 , 왼쪽 대각선 위 중 최소값을 더하기
                if int(matrix[x][y]):
                    dp[x][y] = min(dp[x-1][y], dp[x][y-1], dp[x- 1][y - 1]) + 1
                    maxValue = max(maxValue, dp[x][y])
                else:
                    dp[x][y] = 0

        return maxValue ** 2

Java

class Solution {
    public int maximalSquare(char[][] matrix) {
        // 초기설정
        // 가로세로 길이
        int width = matrix[0].length;
        int height = matrix.length;

        int maxValue = 0; // 최대값

        // DP 초기화
        int[][] dp = new int[height][width];

        // 왼쪽, 위, 왼쪽 대각선 위
        int[] dx = {0, -1, -1};
        int[] dy = {-1, 0, -1};

        /*
        * 0번째 행열 그대로 주입
        */
        for (int i = 0; i < height; i++) {
        dp[i][0] = matrix[i][0] - '0';
        maxValue = Math.max(dp[i][0], maxValue);
        }

        for (int i = 0; i < width; i++) {
        dp[0][i] = matrix[0][i] - '0';
        maxValue = Math.max(dp[0][i], maxValue);
        }

        int fx, fy;


        // (1, 1) 부터 탐색 시작
        for (int x = 1; x < height; x++) {
        for (int y = 1; y < width; y++) {

            // 현재 matrix 위치가 1일 경우 dp 탐색
            if (matrix[x][y] == '1') {
            int value = width + height;
            for (int k = 0; k < 3; k++) {
                fx = x + dx[k];
                fy = y + dy[k];
                value = Math.min(value, dp[fx][fy]);
            }
            dp[x][y] = value + 1; // 탐색 한 것 중 가장 적은 것을 더한다.


            }else{
            dp[x][y] = 0;
            }
            maxValue = Math.max(maxValue, dp[x][y]);
        }
        }

        return maxValue * maxValue;
    }
}