C++로 해결하는 직사각형 면적 합산 문제 (Rectangle Area II)

축에 평행한(axis-aligned) 직사각형들의 목록이 주어졌다고 가정해 봅시다. 각 rectangle[i] = {x1, y1, x2, y2}에서 (x1, y1)은 i번째 직사각형의 왼쪽 아래 꼭짓점 좌표이고, (x2, y2)는 오른쪽 위 꼭짓점 좌표입니다.

우리가 구해야 할 것은 평면 위에서 모든 직사각형이 차지하는 총 면적입니다. 답이 매우 커질 수 있으므로, 결과값을 10^9 + 7로 나눈 나머지를 반환하도록 합니다.

예를 들어 입력이 아래와 같다면,

출력은 6이 됩니다.

문제 접근 방법

이 문제는 스위프 라인(Sweep Line) 기법과 좌표 압축(Coordinate Compression)을 조합하여 효율적으로 해결할 수 있습니다. 전체 알고리즘의 흐름은 다음과 같습니다.

모듈로 상수 m = 10^9 + 7을 설정합니다.
add() 함수를 정의합니다. 두 수 a, b를 받아 ((a mod m) + (b mod m)) mod m을 반환하여 오버플로우를 방지합니다.
compress() 함수를 정의하여 x좌표들을 중복 없이 압축된 인덱스로 매핑합니다.

메인 로직 상세 단계

x좌표 배열 xv를 만들고 모든 직사각형의 x1, x2 값을 삽입한 뒤 정렬합니다.
unique()로 중복을 제거하고, 각 x좌표를 인덱스로 매핑하는 맵 index를 생성합니다.
각 세그먼트의 덮임 여부를 저장할 count 배열을 선언합니다.
각 직사각형마다 두 개의 이벤트를 생성합니다: 하단 변(y1)에는 {y1, x1, x2, 1}, 상단 변(y2)에는 {y2, x1, x2, -1}을 추가합니다.
이벤트 배열을 y좌표 기준으로 정렬합니다.
y축 방향으로 스위프하면서 다음을 반복합니다:
- 현재 y와 이전 y(currentY)의 차이에 현재 덮인 너비(sum)를 곱해 누적 면적(ret)에 더합니다.
- 현재 이벤트의 시그니처(sig)만큼 해당 x구간의 count 값을 증감합니다.
- count 값이 0보다 큰 구간들의 너비를 합산하여 sum을 갱신합니다.
최종적으로 ret mod m을 반환합니다.

구현 코드

아래 C++ 구현을 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
   public:
   lli add(lli a, lli b){
      return ((a % m) + (b % m) % m);
   }
   map<int, int> compress(vector<vector<int> >& v){
      vector<int> temp;
      for (int i = 0; i < v.size(); i++) {
         temp.push_back(v[i][0]);
         temp.push_back(v[i][2]);
      }
      sort(temp.begin(), temp.end());
      map<int, int> ret;
      int idx = 0;
      for (int i = 0; i < temp.size(); i++) {
         if (!ret.count(temp[i])) {
            ret[temp[i]] = idx;
            idx++;
         }
      }
      return ret;
   }
   int rectangleArea(vector<vector<int> >& v){
      vector<int> xv;
      xv.push_back({ 0 });
      for (int i = 0; i < v.size(); i++) {
         xv.push_back(v[i][0]);
         xv.push_back(v[i][2]);
      }
      sort(xv.begin(), xv.end());
      vector<int>::iterator uniItr = unique(xv.begin(), xv.end());
      xv.erase(uniItr, xv.end());
      map<int, int> index;
      int idx = 0;
      for (int i = 0; i < xv.size(); i++) {
         index[xv[i]] = i;
      }
      vector<int> count(index.size());
      vector<vector<int> > x;
      int x1, x2, y1, y2;
      for (int i = 0; i < v.size(); i++) {
         x1 = v[i][0];
         y1 = v[i][1];
         x2 = v[i][2];
         y2 = v[i][3];
         x.push_back({ y1, x1, x2, 1 });
         x.push_back({ y2, x1, x2, -1 });
      }
      sort(x.begin(), x.end());
      lli ret = 0;
      lli sum = 0, currentY = 0;
      for (int i = 0; i < x.size(); i++) {
         lli y = x[i][0];
         x1 = x[i][1];
         x2 = x[i][2];
         int sig = x[i][3];
         ret = add(ret, (y - currentY) * sum);
         currentY = y;
         for (int i = index[x1]; i < index[x2]; i++) {
            count[i] += sig;
         }
         sum = 0;
         for (int i = 0; i < count.size(); i++) {
            if (count[i] > 0) {
               sum += (xv[i + 1] - xv[i]);
            }
         }
      }
      return ret % m;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,2,2},{1,0,2,3},{1,0,3,1}};
   cout << (ob.rectangleArea(v));
}

입력

{{0,0,2,2},{1,0,2,3},{1,0,3,1}}