boj 7626 - 직사각형

목차

개요
요약
설명
코드

 

개요

이 문제는 Segment Tree 자료구조와 Sweeping 알고리즘을 함께 활용하여 풀어야 하는 문제입니다. 추가로 좌표의 범위가 상당히 넓기 때문에 ($0$ ~ $1,000,000,000$) 좌표 압축까지 병행해야 합니다.

 

문제의 Key Idea는 Segment Tree에 어떤 정보를 저장할 것이냐 입니다. 예를 들어, x축으로 Sweeping을 진행한다고 할 때, 직사각형의 넓이를 구하기 위해서는 각 x좌표 별로 직사각형에 포함되는 y영역과 그렇지 않은 영역을 구분해야 합니다.

 

이를 구분하기 위해서 기존 방식의 Segment Tree보다는 구간 Update query를 통해 현재 활성화 된 직사각형의 개수가 몇 개인지 구간 별로 관리하고, 넓이를 단번에 파악할 수 있도록 전체 직사각형 y의 부분 합을 저장하는 변형된 방식을 사용해야 합니다.

 

요약

1) y좌표를 기준으로 좌표 압축을 실행한다.

2) x좌표를 정렬해서 오름차순으로 sweep을 실행한다.

 

모든 직사각형을 탐색할 때 까지 3, 4, 5를 반복

3) x좌표 차이 (너비)와 Segment Tree의 root node에 저장된 높이 합을 곱해서 정답에 추가한다.

4) 직사각형이 시작하는 경우, Segment Tree에 구간 update query를 실행해서 count++ 와 자신의 직사각형의 높이를 기록한다.

5) 직사각형이 끝나는 경우, Segment Tree에 구간 update query를 실행해서 count--를 한다. count가 0인 경우, child node의 부분합으로 높이를 변경한다. (Leaf node일 경우, 0으로 기록한다)

 

설명

다음과 같이 6개의 직사각형 넓이 합을 알고 싶다고 해봅시다. (정답: 7080)

6
30 60 10 124
130 140 44 50
100 110 3 124
10 50 3 44
40 110 16 50
80 90 3 10

위를 그림으로 나타내면 다음과 같습니다.

 

여기서 y좌표의 범위가 0부터 10억까지 가능합니다. Segment Tree의 node를 10억 개 만들 수 없으므로 좌표 압축을 하는 것이 좋겠죠. 유의미한 좌표인 3을 0번으로 기준 삼아 124까지 좌표를 압축하면 아래와 같이 나타낼 수 있습니다.

 

그리고 계산을 통해서 좌표가 압축된 y좌표 사이의 실제 길이도 알 수 있죠. (그림의 우측)

그러면 이제 X축의 왼쪽부터 오른쪽으로 차례대로 Sweep하면서 활성화 된 y축의 길이를 Segment Tree에 저장하면 됩니다.

 

Step 1) x = 10

x좌표가 10일 때를 살펴보면, 직사각형이 시작되고 있습니다. 그렇다면 y좌표 0이상 3미만이 활성화 된 구간이므로 Segment Tree에 저장하고, 차례로 node들을 수정해줍니다.

 

만약 Segment Tree가 오른쪽과 같이 구성되어 있다고 가정합시다. 각 node들은 Y축 실제 길이 / 선분 활성화 개수를 저장합니다.

 

이 상태에서 node들을 수정해가던 중에 1이상 3미만은 leaf node까지 가지 않고, 한꺼번에 표현이 가능한 node가 존재합니다. 이 경우에는 해당 node를 직접 수정하고 child node들은 수정하지 않습니다. Leaf까지 직접 수정해서 전체를 수정하는 방법도 있겠지만, 이 방법이 더 효율적이겠죠?

 

Step 2) x = 30

다음 y축 활성이 변화하는 지점은 x가 30일 때입니다. 이 때, 현재까지 활성화 된 y축 길이의 합 (Segment Tree의 root node)과 x좌표 차이를 곱해서 정답에 더해줍니다.

위에서 검은색으로 칠해진 영역은 계산이 끝난 직사각형입니다.

이제, 새로운 직사각형 1이상 5미만이 등장합니다. 마찬가지로 해당 부분에 맞는 node들을 수정해줍니다.

Step 3) x = 40

다음으로 y축 활성이 변하는 좌표는 x가 40일 때입니다. 마찬가지로 현재까지 활성화 된 y좌표의 길이의 합과 x좌표 차이를 곱해줍니다.

위 그림에서 알 수 있듯이, 2이상 3미만과 3이상 4미만은 각각 다른 sub node들이 담당을 하고 있습니다. 따라서 leaf node까지 탐색하여 수정을 해줘야 합니다.

 

그러나, 이 leaf node들을 수정을 해주더라도 이미 parent node가 활성화 되어 있기 때문에, 재귀적으로 수정해야 할 필요는 없습니다. (즉, 이전 직사각형에 포함되는 영역입니다.)

 

Step 4) x = 50

처음으로 만났던 직사각형이 끝나는 좌표입니다. 먼저, 정답 값을 앞서 했던 방법과 같은 방식으로 update 해줍니다.

앞서 직사각형을 만났던 때를 생각해봅시다. count에 +1을 해주던 방식처럼 구간 업데이트를 통해 count를 1 감소 시킵니다.

특히, 0이상 1미만 구간의 경우에는 count가 0으로 변했으므로 재귀적으로 parent들을 update 해줘야 합니다.

 

Step 5) x = 60

x좌표가 60일 때는 다음과 같이 수정됩니다.

Leaf node가 아니라 subnode의 count가 0이된 경우, Y 길이의 부분합 값은 child들의 합으로 변경해줘야 합니다.

 

Step 6) x = 80

0이상 1 미만의 직사각형이 시작되었으므로 Segment Tree에 반영해줍니다.

 

Step 7) x = 90

Step 8) x = 100

모든 y좌표가 활성화 됩니다. 따라서 root node만 수정해주면 됩니다.

 

Step 9) x = 110

동시에 두 직사각형이 종료됩니다. 차례차례 순서 상관 없이 모두 비활성화 해주면 됩니다.

 

Step 10) x = 130, x = 140

마찬가지로 x좌표가 130일 때 있는 작은 직사각형도 같은 방법으로 해주면 됩니다. 정답은 7020 + 10 * 6

 

7080이 되겠네요.

 

 

코드

#include<stdio.h>
#include<algorithm>
using namespace std;

int N;

class Point{
        public:
        int val;
        int idx;
        int y1;
        int y2;

        bool operator<(Point a) const{
                return this->val < a.val;
        }
};
class Y{
        public:
        int val;
        int idx;

        bool operator<(Y a) const{
                return this->val < a.val;
        }
};

Point x[400002];
Y y[400002];

long long int cnt[1600000];
long long int sum[1600000];
class Tree{
        public:
        Tree(){
                for(int i=0;i<N*8;i++){
                        cnt[i] = 0;
                        sum[i] = 0;
                }

        }
        void update(int left, int right, int start, int end, int k, int val){
                int mid = (start+end)/2;
                int ret = 0;
                if(start >=left && end <= right){
                                cnt[k] += val;
                }else{
                        if(left<=mid) update(left, right, start, mid, k*2, val);
                        if(right>mid) update(left, right, mid+1, end, k*2+1, val);
                }

                if(cnt[k]){
                        sum[k] = y[end+1].val - y[start].val;
                }else{
                        if(start==end) sum[k] = 0;
                        else sum[k] = sum[k*2] + sum[k*2+1];
                }
        }
};
int main(){
        long long int ANS = 0;
        scanf("%d",&N);
        for(int i=0; i<N;i++){
                int a = 2*i, b = 2*i+1;
                scanf("%d %d %d %d",&x[a].val, &x[b].val, &y[a].val, &y[b].val);
                x[a].idx = y[a].idx = a;
                x[b].idx = y[b].idx = b;
        }
        sort(y,y+2*N);

                //Coordinate compression
        for(int i=0;i<2*N;i++){
                int arr_idx = y[i].idx / 2;
                if(y[i].idx %2==0){
                        x[arr_idx*2].y1 = i;
                        x[arr_idx*2+1].y1 = i;
                }else{
                        x[arr_idx*2].y2 = i;
                        x[arr_idx*2+1].y2 = i;
                }
        }

        sort(x,x+2*N);
        for(int i=0;i<2*N;i++){
        }

        Tree *t = new Tree();
        for(int i=0;i<2*N;i++){
                if(i>0){
                        ANS += sum[1] * (x[i].val - x[i-1].val);
                }
                if(x[i].idx % 2 ==0){ //Rectangle start
                        t->update(x[i].y1, x[i].y2-1, 0, 2*N-1,1, 1);
                }else{//Rectangle end
                        t->update(x[i].y1, x[i].y2-1, 0, 2*N-1,1, -1);
                }

        }
        printf("%lld\n",ANS);
        return 0;
}