boj 5419 - 북서풍

목차

개요 요약

개요

설명

코드

---

개요 요약

문제를 풀기위한 key point는 크게 다음과 같습니다.

• 북서풍을 타고 이동할 수 있는 섬의 쌍을 구하기 위해서는 각 섬마다 자신보다 왼쪽이면서 위에 있는 섬의 개수를 구해서 더하면 됩니다.
• 섬의 개수가 방대해서 일일이 구하기에는 시간복잡도가 큽니다. 따라서 sweeping과 segment tree를 활용하여 한 방향으로 섬 하나하나 sweep해가야 합니다. 이 과정에서 조건을 만족하는 섬의 개수를 segment tree를 통해 빠르게 알아냄과 동시에 자신을 segment tree에 등록하면 됩니다.
• Segment tree에 좌표를 사용하기에는 범위가 너무 넓습니다. 따라서 좌표 압축을 한 번 수행해서 20억 개의 원소가 아닌 75,000개의 원소 만으로도 해결할 수 있도록 해야 합니다.

---

개요

이 문제는 북서풍을 타고 섬 여행을 할 수 있는 모든 섬의 쌍의 수를 구하는 문제입니다. 쌍의 수를 구하는 문제이므로 (시작 섬, 도착 섬)의 개수만 구해주면 됩니다. (a→...→z 와 같이 경로의 경우의 수를 구하는 문제가 아닙니다.)

 

섬의 쌍 구하기

살펴보면 어떤 섬 $A$의 좌표를 $(x, y)$라고 했을 때, 섬 $A$로 도달할 수 있는 섬들은 좌표가 $x$보다 작으면서 동시에 $y$좌표는 높아야 합니다. 즉, 섬 $K (a,b)$에서 섬 $A (x,y)$로 가기 위한 조건은 다음과 같습니다.

$$a \le x \ \ and \ \ b \ge y$$

 

이러한 조건을 만족 시키는 섬 $K$의 개수를 구하되, 섬 $A$뿐만 아니라 문제에서 주어진 모든 섬에 대해서 구하고 합하면 됩니다.

Sweeping과 Segment tree를 사용하기

여기서 각각의 섬에서 조건을 만족하는 섬을 일일이 체크하기에는 계산양이 너무 많습니다. 75,000개의 섬이 있는 경우 75,000 * 74,999 개의 연산을 필요로 합니다. 여기서 sweeping과 segment tree를 복합적으로 사용함으로써 이 연산을 획기적으로 줄일 수 있습니다. ($n \ log\ n)$

 

좌표 압축

이 문제에서는 추가적으로, 좌표의 범위가 너무 넓습니다 (-10억 ~ 10억). Segment tree를 사용하는데 있어서 배열을 20억개 만들어 놓을 수는 없으므로 좌표 압축이 필요합니다.

---

설명

간단하게 다음과 같은 예제로 살펴보도록 하죠

5
15 7
-10 -10
-10 10
10 -10
10 10

이 예제를 그려보면 다음과 같습니다.

여기서 우리는 문제 해결을 위해 x좌표가 작은 곳에서 증가하는 방향으로 sweeping하겠습니다. 가장 먼저 해야 하는 것은 좌표 압축입니다. 이런 경우, 좌표 압축은 y축에 대해서만 해주면 됩니다.

좌표 압축

좌표 압축을 수행하면 섬의 좌표는 다음과 같이 변화합니다.

좌표 압축은 간단히 순위로 바꿔주1면 됩니다. 단순히 y좌표의 정렬 순서로 치환합니다. (-10, 7, 10) → (0, 1, 2)

Segment tree와 Sweeping

Segment tree의 node는 현재까지 처리한 섬들의 y좌표 개수를 부분 합 tree로 관리할 예정입니다. 위의 예제를 그대로 하나씩 처리해보도록 하죠.

 

먼저 사전에 정렬이 되어있어야 합니다. x좌표는 오름차순으로, 그리고 x좌표가 같다면 y좌표는 내림차순으로 되어있어야 합니다. 그러면 순서는 다음과 같겠죠?

Step 1

이제 1번부터 살펴볼까요? 먼저 섬을 기준으로 자신보다 좌상단에 섬이 있는 지 살펴봐야 합니다.

이는 Segment tree의 Search로 자신의 y좌표인 2 이상이 있는 지 보면 됩니다.

이는 segment tree에서 부분합 ( 2 ~ 2 ) 을 살펴보면 됩니다. 그림에서 노란색 노드입니다. 그러나 처음이라 없으므로 값은 0입니다.

 

이제 섬 1번을 segment tree에 등록시켜줍니다.

그러면 위에서 빨간색 글씨처럼 segment tree의 node 값들이 바뀝니다.

 

Step 2

이제 2번 섬을 살펴봅니다. 자신의 섬보다 위쪽에 있는 섬의 개수를 구합니다. 마찬가지로 segment tree에서 부분합 ( 0 ~ 2 ) 을 살펴보면 됩니다. 이 구간은 그림에서 노란색 노드입니다.

여기서 값이 1입니다. 이 말은, 어떤 섬에서 2번 섬으로 올 수 있는 섬이 1개 있다는 의미입니다. 따라서 정답에 1을 더해줍니다.

이제 자신의 섬을 segment tree에 등록시켜 줍니다.

이제 대략 감이 오셨으리라 생각합니다. step 3부터 step 5까지는 그림 만으로 간단히 살펴보겠습니다.

Step 3

자신보다 상단에 있는 섬의 개수를 구해줍니다. segment tree를 search하면 1의 값이 나옵니다. 이를 정답에 더해줍니다.

마찬가지로 섬 3번을 segment tree에 등록 시켜줍니다.

Step 4

마찬가지로 자신보다 위에 있는 섬의 개수를 구해줍니다. 검색하면 3이 나오네요. 이를 정답에 더해줍니다.

이제 자신을 segment tree에 등록합니다.

Step 5

마지막으로 step 5입니다. 자신보다 상단에 있는 섬의 개수는 segment tree를 조사하면 2가 나오겠죠. 이를 정답에 더해주면 5+2 = 7이 됩니다.

 

이렇게 자신보다 좌상단에 있는 섬을 쉽게 구할 수 있습니다. 사실 살펴보면 segment tree는 자기보다 상단에 있는 섬의 개수만 저장합니다. 반면, 자신보다 좌측에 있는지는 조사하지 않지요. 그러나 이는 sweeping 과정에서 왼쪽부터 오른쪽으로 수행하므로 segment tree를 search하는 시점에서의 값은 모든 섬이 자신보다 좌측에 있음을 보장할 수 있습니다.

---

코드

※주의할 점

1. Test case가 여러개이므로 초기화에 유의!

#include<stdio.h>
#include<algorithm>
#include<string.h>
#define IMAX 2147483647

using namespace std;
int T;
int n;

typedef struct Invec{
        int x,y,index;
}InVec;
InVec input[75000];

bool cmpY(const InVec& a, const InVec& b){
        return a.y > b.y;
}

typedef struct vec{
        int x,y;
}Vec;
bool cmp(const Vec &a, const Vec &b){
        return a.x < b.x || a.x == b.x && a.y < b.y;
}
Vec arr[75000];

void compress(){

        sort(input, input+n, cmpY);
        int rank = -1, prev = IMAX;
        for(int i=0; i<n ; i++){
                if(prev != input[i].y) rank++;
                arr[input[i].index].y = rank;
                arr[input[i].index].x = input[i].x;
                prev = input[i].y;
        }
        sort(arr, arr+n, cmp);
}

class Tree{
        public:
        int node[300000];

        void Insert(int cur, int left, int right, int index, int val){
                        if(left==right){
                                node[cur] += val;
                                return;
                        }

                        int mid = (left+right)/2;
                        if(index <= mid) Insert(cur*2, left, mid, index, val);
                        else Insert(cur*2+1, mid+1, right, index, val);
                        node[cur] = node[cur*2] + node[cur*2+1];
        }
        int Search(int cur, int left, int right, int start, int end){
                if(left<= start && right >= end){
                        return node[cur];
                }
                int mid = (start+end)/2;
                int sum = 0;
                if(left<=mid)
                        sum += Search(cur*2, left, right, start, mid);
                if(right>mid)
                        sum += Search(cur*2+1, left, right, mid+1, end);
                return sum;
        }
};
int main(){
        scanf("%d",&T);
        while(T--){
                scanf("%d",&n);
                Tree* t = new Tree();
                for(int i=0;i<n;i++){
                        scanf("%d %d",&input[i].x, &input[i].y);
                        input[i].index = i;
                }
                compress();

                long ans = 0;
                for(int i=0;i<n;i++){
                        int ret = t->Search(1, 0, arr[i].y, 0, n-1);
                        t->Insert(1, 0, n-1, arr[i].y, 1);
                        ans+=ret;
                }
                printf("%ld\n",ans);
                for(int i=0;i<n;i++){
                        input[i].x = 0;
                        input[i].y = 0;
                        input[i].index = 0;
                        arr[i].x = 0;
                        arr[i].y = 0;
                }
                delete t;
        }
        return 0;
}