(25.03.29) 최대 사각형 구하기 알고리즘 : 히스토그램, DP, 비트마스크

 

Maximal Rectangle 이란 알고리즘을 비트마스크와 DP를 사용하는 예제로 풀게 되었는데,

상당히 이해하는데 많은 시간이 걸렸기에.. 일단 완벽하게 이해를 하는것 보다 이렇게 작동되는지 알고 코드 흐름을 기억하는 수 밖에 없는 것 같다.

 

추후에 언젠가 보여질 수 있기 때문에 반복해서 코드를 기억해서 작성하기도 했다.

---

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 6 Explanation: The maximal rectangle is shown in the above picture.

 

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        // 누적 높이 구하기
        int[] heights = new int[cols];
        int maxArea = 0;
        for(char[] row : matrix) {
            for(int i = 0; i < cols; i++) {
                heights[i] = (row[i] == '1') ? heights[i] + 1 : 0;
            }

            // 최대 넓이 갱신하기
            maxArea = Math.max(maxArea, getMaxRectangle(heights));
        }

        return maxArea;
    }

    public int getMaxRectangle(int[] heights) {
        int length = heights.length;
        int maxArea = 0;

        // stack 써서 최대 사각형 구하기 알고리즘 실행
        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i <= length; i++) {
            // 맨 마지막 고려
            int currentHeight = (i == length) ? 0 : heights[i];
            
            while(!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
                // 최댓값갱신
                int index = stack.pop();

                int height = heights[index];

                // stack 비원진 것 고려 -> 처음 ~ i 까지 거리
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                
                maxArea = Math.max(maxArea, height * width);
            }
 
            stack.push(i);
        }

        return maxArea;
    }
}

• matrix를 순회하면서 heights 배열을 누적해서 반복
  • 연속한 1일 수록 heights 누적하고, 중간에 0이 나오면 초기화 하면서 행을 진행
• getMaxRectangle
  • heights 각 행의 히스토그램이라 생각하고 가장 큰 사각형 넓이를 구하고, 행을 더하면서 각 행에서의 최대 넓이 중 가장 넓은 넓이를 선택
  • Monotonic Stack 기법 활용
    1. 히스토그램(heights) 왼쪽 ~ 끝+1 까지 진행
       • 여기서 +1은 stack에 넣어서 사용하지 않은 히스토그램 막대를 써서 최대의 넓이를 구하는 방식
    2. 가장 처음 히스토그램은 stack에 인덱스를 push
    3. 다음 히스토그램 크기가 클 경우 → stack에 인덱스 push
    4. 다음 히스토그램 크기가 작은 경우
       • stack pop 의 높이보다 다음 히스토그램이 커질 때 까지 계속 진행
       • 다은 히스토그램 인덱스 - stack.peek() - 1 을 너비, 히스토그램 높이를 곱해서 넓이를 만듬
    5. int currentHeight = (i == length) ? 0 : heights[i];
       • 마지막 인덱스 +1 은 높이가 0이기 때문에 겨진 stack 에 있는 히스토그램은 0 ~ i(마지막 인덱스 +1) 까지를 넓이로 마지막 직사각형들을 마무리해서 계산
• 결국 행이 늘어가면서 만들 수 있는 모든 최대 직사각형을 모두 구한 후, 그 중에서 가장 큰것을 고르면, 전체 부분의 최대 직사각형을 구할 수 있음

참고 영상

 

 

---

Monotonic Stack 기법을 활용한 최대 넓이 구하기는 생각보다 생소해서 결국에 유튜브를 찾아보면서 이해하려고 했다.

하지만, 지금까지 BFS 로 브루털하게 풀었던 과거의 문제도 기억나면서
자료구조의 활용도 연습하면서 몇번 연습을 더 하려고 한다.