[BOJ] 5419: 북서풍 (C/C++)

문제 5419번: 북서풍

강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다.

작은 섬이 여러 개 있는 바다가 있다. 섬은 좌표 평면의 한 점으로 나타낼 수 있다. y 좌표가 증가하는 방향은 북쪽, x좌표가 증가하는 방향은 동쪽이다. 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫째 줄에는 섬의 수 n (1 ≤ n ≤ 75’000)이 주어진다. 다음 n개 줄에는 각 섬의 좌표 \(x_i, y_i\)가 주어진다. 두 섬의 좌표가 같은 경우는 없다. \((-10^9 ≤ x_i,\;y_i ≤ 10^9)\)

각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

문제분석

문제 요구사항

• 북서풍을 타고 항해할 수 있는 섬의 쌍을 찾아야 한다.
  • x의 경우 크거나 같은, y의 경우 작거나 같은 섬은 쌍이 만들어진다.

섬의 좌표에 대하여 효율적으로 비교할 수 있게 섬을 정렬 시킨 후, Sweeping 알고리즘을 도입하여 풀이한다.

구현

섬의 좌표를 처음 y좌표에 대하여 정렬 한 후, y좌표에 대하여 Coordination Compression을 진행 한 후, x좌표에 대하여 정렬 한다.
그 후 Sweeping 알고리즘을 통하여 섬들을 탐색 하면서, y좌표를 기반으로 하여 섬의 갯수를 반환하는 Segment Tree에 섬을 집어 넣은 후, Segment Tree를 활용하여 쌍의 갯수를 반환하고, 탐색이 끝난 후 Segment Tree의 해당 섬을 집어넣는다.

증명

해당 구현의 가장 큰 방점인 Sweeping 알고리즘에 대하여 해당 위키피디아 링크를 참고하기 바란다.

• Sweep line algorithm

해당 문제에서 가장 중요한 것은 Sweeping 하는 직선을 기준으로 조건을 만족하는 쌍을 놓치지 않는 것이다.
Sweeping 알고리즘을 y축에 평행한 직선을 x좌표의 음수 쪽에서 양수 쪽으로 직선을 움직인다고 생각하며 적용한다.
그럼으로 x축을 기준으로 Ascending Order(오름차순)으로 정렬하고, 만약 x축 좌표가 같다면 y축 좌표기준 Descending Order(내림차순)를 적용한다.

해당방식으로 정렬시, Sweeping 직선을 기준으로 조건을 만족하는 쌍을 놓치지 않기 때문에 유효한 알고리즘임을 증명 할 수 있다.

이때, y의 가능 범위가 2’000’000’000 이기 때문에 Segment Tree를 만들시 많은 메모리 공간이 낭비 됨으로,
맨 처음에 y축 좌표를 기준으로 정렬 시키어 y축 좌표에 대한 좌표압축을 진행한 후 압축된 y좌표로 Segment Tree를 만든다.

코드

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

struct Island {
  int x;
  int y;
};

struct FirstCompare {
  const bool operator()(const Island& li, const Island& ri) {
    return li.y != ri.y ? li.y < ri.y : li.x > ri.x;
  }
};

struct SecondCompare {
  const bool operator()(const Island& li, const Island& ri) {
    return li.x != ri.x ? li.x < ri.x : li.y > ri.y;
  }
};

struct SegTree {
 private:
  int nmax;
  std::array<int, 262'144> tree;

 public:
  void Init(const int N) {
    nmax = BitCeil(N);
    std::fill_n(tree.begin(), nmax << 1, 0);
    return;
  }

  void Insert(const int num) {
    for (int i = (num + nmax); i > 0; i >>= 1) {
      tree[i]++;
    }
    tree[0]++;
    return;
  }

  const int Query(int right) {
    int left = 0;
    int left_value = 0;
    int right_value = 0;
    for (left += nmax, right += nmax + 1; left < right;
         left >>= 1, right >>= 1) {
      if (left & 1) {
        left_value += tree[left++];
      }
      if (right & 1) {
        right_value += tree[--right];
      }
    }
    return left_value + right_value;
  }

 private:
  const int BitCeil(int size) {
    int output_size = 1;
    while (size != 0) {
      output_size <<= 1;
      size >>= 1;
    }
    return output_size;
  }
};

std::istream& operator>>(std::istream& is, Island& i) {
  is >> i.x >> i.y;
  return is;
}

std::ostream& operator<<(std::ostream& os, const Island& i) {
  os << i.x << " " << i.y;
  return os;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);

  int T;
  std::cin >> T;

  std::array<Island, 75000> islands;
  SegTree tree;

  for (int test_case = 0; test_case < T; ++test_case) {
    int N;
    std::cin >> N;

    for (int i = 0; i < N; ++i) {
      std::cin >> islands[i];
    }

    std::sort(islands.begin(), islands.begin() + N, FirstCompare());
    for (int i = 0; i < N; ++i) {
      islands[i].y = i;
    }
    std::sort(islands.begin(), islands.begin() + N, SecondCompare());

    long long ans = 0;
    tree.Init(N);
    for (int i = 0; i < N; ++i) {
      ans += i - tree.Query(islands[i].y);
      tree.Insert(islands[i].y);
    }

    std::cout << ans << "\n";
  }

  return 0;
}