[BOJ 3392] 화성 지도

백준 3392번 화성 지도

https://www.acmicpc.net/problem/3392

3392번: 화성 지도

---

문제

변이 각각 x축, y축으로 평행한 직사각형이 N개가 주어짐 (N <= 10,000)

(0 <= 좌표 <= 30,000)

 

N개의 직사각형의 면적을 모두 더하는 문제

(겹치는 부분은 한번만 계산해야 함)

---

풀이

직사각형이 입력으로 주어질 때 마다 주어진 영역을 2차원 배열을 만들어 표시해줍니다.

그리고 1이상인 좌표가 있을 때마다 정답에 +1을 더해주면 간단히 해결될 것처럼 보입니다.

 

하지만 이는 공간적으로든, 시간적으로든 문제 제한 안에 들어오지 못하는 수치입니다.

 

좌표에 해당하는 2차원 배열을 만드려면 30000 * 30000 배열이 필요합니다.

이는 메모리 제한 128MB를 초과하는 수치입니다.

 

직사각형 하나를 2차원 배열에 나타내려면 최대 30000 * 30000 의 시간이 듭니다.

이를 N번 해야하므로 최대 O(10000 * 30000 * 30000) 이 드는데 이는 시간 제한 1초를 초과하는 수치입니다.

 

따라서 더 빠른 풀이를 찾아야 합니다.

---

스위핑 알고리즘으로 이 문제를 풀 수 있습니다.

 

문제에 주어진 입력 예시를 토대로 풀이를 떠올려보겠습니다.

 

이를 3개의 영역으로 나눌 수 있습니다.

그리고 이 영역을 다 더해주면 됩니다.

(5 * 10) + (5 * 20) + (5 * 15) = 225

---

위와 같이 영역을 나누려면, y축에 평행한 직선을 다 뽑아냅니다.

하나의 직사각형에는 y축에 평행한 직선이 2개 나오기 때문에 위 그림에서는 총 4개의 직선이 나올 것입니다.

 

• 공통 사항
  • (y 좌표의 cnt가 +1 이상인 점의 개수) * (현재 x 좌표 - 직전 x 좌표) 를 정답에 더해줍니다.
• 주황색 선
  • 직사각형이 시작하는 선
  • 직선이 나타내는 y 좌표 범위에 cnt를 전부 +1을 해줍니다.
• 파랑색 선
  • 직사각형이 끝나는 선
  • 직선이 나타내는 y 좌표 범위에 cnt를 전부 -1을 해줍니다.

 

이를 토대로 정답이 제대로 나오는지 확인해보겠습니다.

x 좌표가 작은 line 부터 번호를 순차적으로 매겼습니다.

정답이 225가 나오는 것을 확인할 수 있습니다.

 

모든 직선을 하나만 살펴보면서 정답을 구하기 때문에 스위핑 알고리즘을 사용했다고 볼 수 있습니다.

---

라인 스위핑 알고리즘으로 이 문제를 풀 수 있다는 것을 알아냈습니다.

하지만, y좌표와 관련된 작업(update, find)을 빠르게 찾지 못한다면 이 역시 시간 제한 안에 못 들어올 수 있습니다.

 

얼핏보면 레이지 프로퍼게이션을 사용한 세그먼트 트리로 구간 합을 구하면 될 것 같습니다.

이는 y 좌표에 +1이나 -1을 더할 때는 상관없지만,

y 좌표의 cnt가 +1 이상인 좌표를 구할 때는 구간 합으로 가져오면 안됩니다.

 

위의 예제에서 line2 까지 진행했다고 생각해보겠습니다.

line1에 의해 10 ~ 20의 y좌표에 +1을 더해줬고, line2에 의해 15~30의 y좌표에 +1을 더해줬습니다.

 

여기서 구간 합으로 값을 가져오면 25(20 - 10, 30 - 15)의 값을 가져옵니다.

하지만 우리가 가져와야 하는 값은 20(30 - 10)입니다.

---

세그먼트 트리를 조금 변형해보겠습니다.

세그먼트 트리 각각의 노드에는 cnt와 sum 두 가지 변수가 있습니다.

 

cnt는 line에 의해 y좌표에 +1이나 -1을 더해줘야 하는데, 이를 저장한 값입니다.

즉, cnt가 1 이상이라면 해당 노드가 포함하는 구간의 y좌표는 전부 cnt가 +1 이상 이라는 의미입니다.

 

sum은 y좌표의 cnt가 +1 이상인 좌표들의 개수를 저장한 값입니다.

해당 노드의 cnt가 1 이상이라면 해당 노드가 포함하는 구간의 길이를 저장하면 됩니다.

 

이렇게 설정해두면, 레이지 프로퍼게이션을 사용하지 않고도 이를 풀 수 있습니다.

자세한건 아래 코드를 확인해주세요.

---

코드

#include <cstdio>

const int MAX = 3e4 + 1;
const int SIZE = 2e4 + 4;

struct Data {
	int x, y1, y2, opt;

	bool operator<(Data O) {
		return x < O.x;
	}
}arr[SIZE];

struct Sort {
	Data temp[SIZE];

	void merge(int l, int r, int m) {
		int i = l, j = m + 1, k = l;
		while (i <= m && j <= r)
			temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
		while (i <= m) temp[k++] = arr[i++];
		while (j <= r) temp[k++] = arr[j++];

		for (i = l; i <= r; ++i) arr[i] = temp[i];
	}

	void divide(int l, int r) {
		if (l == r) return;

		int m = l + r >> 1;
		divide(l, m);
		divide(m + 1, r);
		merge(l, r, m);
	}

	void work(int N) {
		divide(0, N - 1);
	}
}sort;

struct Segment {
	int sum[MAX * 4], cnt[MAX * 4];

	void update(int l, int r, int n, int ul, int ur, int v) {
		if (ur < l || r < ul) return;

		if (ul <= l && r <= ur) cnt[n] += v;
		else {
			int m = l + r >> 1;
			update(l, m, n << 1, ul, ur, v);
			update(m + 1, r, n << 1 | 1, ul, ur, v);
		}

		if (cnt[n]) sum[n] = r - l + 1;
		else sum[n] = sum[n << 1] + sum[n << 1 | 1];
	}

	inline int get() { return sum[1]; }
}seg;

int solve(int N) {
	sort.work(N);
	int ret = 0;

	for (register int i = 0; i < N; ++i) {
		if (i > 0) ret += seg.get() * (arr[i].x - arr[i - 1].x);
		seg.update(0, MAX, 1, arr[i].y1 + 1, arr[i].y2, arr[i].opt);
	}

	return ret;
}

int main()
{
	//freopen("input.txt", "r", stdin);

	int N, x1, y1, x2, y2;
	scanf("%d", &N);

	for (register int i = 0; i < N; ++i) {
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		arr[i << 1] = { x1, y1, y2, 1 };
		arr[i << 1 | 1] = { x2, y1, y2, -1 };
	}

	printf("%d\n", solve(2 * N));
}