[BOJ 5536] 물고기의 서식 범위

백준 문제 링크

🔍 문제 분석

어떠한 구간이 주어졌을 때, 겹쳐있는 구간의 수 및 길이는 라인 스위핑 알고리즘을 통해 쉽게 구할 수 있다. 본 문제는 삼차원으로 범위가 주어졌으므로, 일차원부터 풀이를 확장해간다.

1. 일차원 구간

• 일차원 구간은 범위의 왼쪽 끝과 오른쪽 끝을 분리한 뒤, 각각 배열에 삽입한다. 배열을 정렬한 뒤, 앞에서부터 뒤로 차례로 순회하며 범위의 왼쪽 끝일 경우 ++cnt를, 오른쪽 끝일 경우 --cnt를 함으로써 겹쳐있는 구간의 수를 알 수 있다.
• 위와 같은 방법으로 겹쳐있는 구간의 수를 구한 뒤, cnt >= K를 만족하는 모든 배열의 원소에 대하여 다음 원소까지의 길이를 합하면 K개 이상 겹쳐있는 구간의 길이를 구할 수 있다.
• K=3의 경우, 위 예시에서 x3, x4일 때 조건이 만족되므로 x3' - x3, x1' - x4가 결과에 더해진다.

  2. 이차원 구간

• 이차원 구간도 x값에 대하여 일차원 구간과 동일하게 진행한다. 만약 cnt >= K를 만족하는 구간 [x1, x2]를 발견하면, 해당 구간에 속해있는 y값들에 대해서 위와 동일한 방식으로 cnt >= K를 만족하는 구간의 길이의 합을 구한다. 이 구간의 길이를 len이라 한다면 해당 부분의 넓이는 (x2 - x1) * len으로 계산할 수 있다.

3. 삼차원 구간

• 위 아이디어를 종합하면 삼차원 구간으로의 확장도 어렵지 않다. cnt >= K를 만족하는 구간 [x1, x2]의 존재하는 y값들에 대해서 cnt >= K를 만족하는 모든 구간 [y1, y2]를 찾는다. 이후, 각 구간 내에 존재하는 z값들에 대해서 cnt >= K를 만족하는 구간의 합을 찾는다. 이 구간의 합은 y값 구간의 길이와 곱해져서 넓이가 되고, 모두 더해진 넓이는 x값 구간의 길이와 곱해져 부피가 된다. 이 과정은 재귀적으로 구현할 수 있다.

💻 코드 구현

#include <bits/stdc++.h>

#define fastio cin.tie(0)->ios::sync_with_stdio(0)

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
using vpi = vector<pi>;

constexpr int MAX = 50;

int N, K, coord[MAX][2][3];

ll solve(set<int> cands, int depth) {
    if (depth >= 3) return 1;
    vpi sweep;
    for (auto idx : cands) {
        sweep.emplace_back(idx, 0);
        sweep.emplace_back(idx, 1);
    }
    auto cmp = [&] (pi lhs, pi rhs) {
        int lhs_pos = coord[lhs.first][lhs.second][depth];
        int rhs_pos = coord[rhs.first][rhs.second][depth];
        if (lhs_pos == rhs_pos) {
            return lhs.second > rhs.second;
        }
        return lhs_pos < rhs_pos;
    };
    sort(sweep.begin(), sweep.end(), cmp);
    set<int> next_cands;
    int cnt = 0;
    ll ret = 0;
    for (int i = 0; i < sweep.size(); ++i) {
        auto [idx, x] = sweep[i];
        if (x == 0) {
            ++cnt;
            next_cands.insert(idx);
        } else {
            --cnt;
            next_cands.erase(idx);
        }
        if (cnt >= K) {
            auto [_idx, _x] = sweep[i + 1];
            ret +=
                (coord[_idx][_x][depth] - coord[idx][x][depth]) *
                solve(next_cands, depth + 1);
        }
    }
    return ret;
}

int main() {
    fastio;

    cin >> N >> K;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 3; ++k) {
                cin >> coord[i][j][k];
            }
        }
    }
    set<int> cands;
    for (int i = 0; i < N; ++i) cands.insert(i);
    cout << solve(cands, 0);
}

📝 코드 설명

• depth = 0은 x값들의 구간을, depth = 1은 y값들의 구간을, depth = 2는 z값들의 구간을 나타낸다.
• solve(cands, 0): cnt >= K인 xyz평면의 존재하는 직육면체들의 부피의 합
• solve(cands, 1): cnt >= K인 x값의 구간에 대해서 해당 구간 내의 존재하는 cnt >= K인 yz평면에 존재하는 직사각형들의 넓이의 합
• solve(cands, 2): cnt >= K인 y값의 구간에 대해서 해당 구간 내의 존재하는 cnt >= K인 z값 구간 길이의 합

🔧 트러블 슈팅

• 좌표의 최대 범위가 1e6이므로 부피는 최대 1e18이 될 수 있다. 따라서, 64bit 정수형을 활용한다.