[알고리즘] 백준 5419 북서풍

📖문제

5419 북서풍

💡구상

위와 같은 네 섬이 존재한다면, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 어떻게 구해야 할까?

각 섬마다 북,서쪽에 섬이 몇개 존재하는지 파악하면 전체 쌍을 구할 수 있다.

하지만 문제의 조건을 살펴보면 섬이 최대 75000개이므로, 완탐기준 75000x75000 대략 56억으로 시간복잡도를 초과한다.

그러므로 펜윅트리를 사용하여 시간복잡도를 줄여보자.

먼저 예시에서 각 좌표를 x축 기준 정렬하면 위와 같다. 하지만 우리는 최북단, 최서단이 시작점이 되어야 하기 때문에, x,-y 좌표를 기준으로 정렬한다.

(-3,-3) 점을 탐색하였을때는 (-3,3)이 체크되어야 하지만 이때 (-3,3)은 등록되지 않았기 때문에 최북단, 최서단이 시작점으로 되어야 한다.

다음으로 각 좌표를 -y 좌표 기준으로 정렬시키고, 정렬한 순서에 해당하는 인덱스에 펜윅트리를 갱신하면서 계산해가면 로직이 완성된다.

-y좌표로 정렬한 순서가 펜윅트리의 인덱스가 되는 이유는 현재 북서쪽에 몇개의 섬이 있는지 파악해야하는데, 펜윅트리의 합은 자신의 인덱스보다 낮은 인덱스에 영향을 받기 때문에, 낮은 인덱스부터 갱신시키는 것이다.

코드로 살펴보자.

🔍코드

#include <bits/stdc++.h>
#define max_n 75004
typedef long long ll;
using namespace std;
int n, x, y, t;
vector<int> tree, _y;
vector<pair<int, int>> a;
int sum (int idx){
    int ret = 0;
    while(idx > 0){
        ret += tree[idx];
        idx -= (idx & -idx);
    }
    return ret;
}
void update(int pos, int value){
    int idx = pos;
    while(idx <= n){
        tree[idx] += value;
        idx += (idx & -idx);
    }
    return;
}
// 인덱스 검색 
int find_index(int value){
    int lo = 0, hi = _y.size() - 1;
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        if(_y[mid] == value) return mid;
        if(_y[mid] < value) lo = mid + 1;
        else hi = mid - 1;
    }
}
int main() {
    cin >>t;
    while(t--){
        cin >> n;
        // 자료구조 초기화 
        a.clear(); _y.clear(); tree.clear();
        tree.resize(n + 1);
        for(int i = 0; i < n; i++){
            cin >> x >> y;
            a.push_back({x, y * -1});
            _y.push_back(y * -1);
        }
        // x축 정렬 
        sort(a.begin(), a.end());
        // y축 정렬 
        sort(_y.begin(), _y.end());
        ll ret = 0;
        // 초기값 업데이트 
        update(find_index(a[0].second) + 1, 1); 
        for(int i = 1; i < n; i++){
            int idx = find_index(a[i].second) + 1;
            ret += sum(idx);update(idx, 1);
        }
        cout << ret << "\n";
    }
	return 0;
}

자료구조 초기화

// 자료구조 초기화 
a.clear(); _y.clear(); tree.clear();
tree.resize(n + 1);

t번 로직을 진행해야하므로, 로직이 진행될때마다 사용한 벡터를 초기화 시켜야 한다.

특히 펜윅트리는 미리 사이즈를 할당시켜야 사용할 수 있으므로 이에 주의하자.

인덱스 검색

// 인덱스 검색 
int find_index(int value){
    int lo = 0, hi = _y.size() - 1;
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        if(_y[mid] == value) return mid;
        if(_y[mid] < value) lo = mid + 1;
        else hi = mid - 1;
    }
}

-y좌표로 정렬한 인덱스를 기준으로 펜윅트리에 업데이트하는데, 현재 문제의 조건으론 섬의 좌표가 (-10^9 <= x,y <= 10^9) 이므로 일반적인 탐색으로는 시간복잡도를 초과한다.

그러므로 이분탐색을 이용한 인덱스 검색을 구현하자.

업데이트 & 갯수 구하기

for(int i = 1; i < n; i++){
    int idx = find_index(a[i].second) + 1;
	ret += sum(idx);update(idx, 1);
}

sum을 먼저하고 update를 할 경우 자기 자신도 갯수에 포함되므로, 반드시 sum을 먼저 하고 update를 진행해야한다.

🔥배운 점

알고리즘 문제를 풀면서 가장 고민을 많이 하고, 이해하려고 시간을 많이 쓴 어려운 문제인것 같다.
로직을 어떻게 구현해야 할지 생각이 나지 않는다면, 정렬했을때 해당 로직이 어떻게 달라지는지 생각하다보면 해결점이 나오는것 같다. 끝까지 고민해보자!