백준 8017번 [Parcel](C++) -yes6686- 티스토리

백준 문제 풀이: 8017 [Zero Rectangle]

---

문제 링크: https://www.acmicpc.net/problem/8017

문제 설명:

주어진 n × n 크기의 행렬에서 0으로만 이루어진 가장 큰 직사각형의 넓이를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <stack>
using namespace std;

int arrR[2001][2001]; // 각 열에서 연속된 0의 개수를 저장
int arr[2001][2001]; // 원본 행렬

stack<pair<int, int>> st; // 스택을 사용한 히스토그램 방식

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 입력 및 초기화
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (i == 0) {
                if (arr[i][j] == 0) {
                    arrR[i][j] = 1;
                }
            }
        }
    }

    // 각 열에서 연속된 0의 개수를 누적 저장
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            if (arr[j][i] == 0) {
                arrR[j][i] = arrR[j - 1][i] + 1;
            }
        }
    }

    int ans = 0;

    // 히스토그램 방식으로 최대 직사각형 넓이 계산
    for (int i = 0; i < n; i++) {
        while (!st.empty()) st.pop(); // 스택 초기화
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 1) { // 1이 나오면 현재 스택을 정리
                while (!st.empty()) {
                    ans = max(ans, st.top().first * (j - st.top().second));
                    st.pop();
                }
            } else {
                if (st.empty()) {
                    st.push({ arrR[i][j], j });
                    ans = max(ans, arrR[i][j]);
                } else {
                    int v, vi = j;
                    while (!st.empty()) {
                        if (st.top().first > arrR[i][j]) {
                            v = st.top().first;
                            vi = st.top().second;
                            st.pop();
                            ans = max(ans, v * (j - vi));
                        } else {
                            break;
                        }
                    }
                    st.push({ arrR[i][j], vi });
                }
            }
        }
    }

    cout << ans << '\n'; // 최대 직사각형 넓이 출력
}

예제 입력:

4
0 0 1 0
0 0 1 1
1 0 0 0
0 0 0 0

예제 출력:

6

---

코드 설명

• 핵심 알고리즘: Largest Rectangle in Histogram을 활용하여 연속된 0의 개수를 기반으로 최대 직사각형 넓이를 계산
• 구현 세부사항:
  • 각 열에서 연속된 0의 개수를 누적하여 arrR 배열을 구성
  • 각 행을 히스토그램으로 간주하고, 스택을 활용하여 최대 직사각형을 찾음
  • 스택을 이용한 히스토그램 방식으로 현재까지의 최대 넓이를 갱신
• 시간 복잡도: O(N²), 각 행마다 히스토그램 계산을 수행

---

결과

주어진 행렬에서 0으로 이루어진 최대 직사각형의 넓이를 효율적으로 계산합니다. 히스토그램을 활용한 DP 및 스택 알고리즘을 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!