스위핑 알고리즘

보통 배열의 모든 원소를 앞에서부터 끝까지 한 번만 쭉 훑어보면서 문제를 해결하는 것을 스위핑 알고리즘이라고 합니다.

배열의 모든 원소를 한 번씩 훑어보는데 $O(n)$ 시간이 걸리지만 그전에 보통 정렬을 하기 때문에 총 $O(nlogn)$ 시간이 걸리게 됩니다.

스위핑의 가장 어려운 점은 훑어보기 전에 어떻게 정렬해야 하는지 알아차리는 것입니다.

가장 기본적인 방법은 배열의 모든 원소를 오름차순으로 정렬하는 것입니다.

백준 2170번: 선 긋기

배열에 선의 시작점과 끝점을 넣어주고 시작점을 기준으로 오름차순 정렬합니다.

for (int i = 0; i < n; ++i) { 
	v.push_back({x, y});
}
std::sort(v.begin(), v.end());

시작은 처음 선의 양 끝을 기준으로 start와 end를 설정합니다.

auto [start, end] = v[0];

이후 하나씩 다음 선들을 살펴보면서 선의 시작점이 end 보다 크다면 (즉, 선이 겹치지 않는다면) 지금까지의 선들의 길이를 저장하고 start와 end를 현재 선으로 갱신합니다.

선이 겹치거나 포함된다면 현재 선의 끝부분과 end를 비교하여 큰 값으로 end를 갱신합니다.

마지막으로 한 번 더 시작점과 끝점의 길이를 저장해 주면 됩니다.

for (int i = 1; i < n; ++i) {
	auto [x, y] = v[i];
	if (x > end) {
		ans += end - start;
		start = x;
		end = y;
	}
	else {
		end = std::max(end, y);
	}
}
ans += end - start;

백준 13334번: 철로

배열에 선의 시작점과 끝점을 넣고 끝점을 기준으로 오름차순 정렬합니다.

for (int i = 0; i < n; ++i) {
	v[i] = {b, a}; // 끝, 시작
}
std::sort(v.begin(), v.end());

이후 선을 하나씩 살펴보면서 선의 길이가 d보다 같거나 작은 경우에만 선의 시작점을 최소 우선순위 큐에 넣습니다.

for (int i = 0; i < n; ++i) {
	auto [y, x] = v[i];
	if (y - x <= d) {
		pq.push(x);
	} else {
		continue;
	}

우선순위 큐에 있는 맨 위의 원소를 하나씩 살펴보면서 현재 선의 끝점과 거리가 철로의 길이보다 큰 원소를 모두 제거합니다.

그리고 현재 우선순위 큐에 남아있는 원소의 개수를 정답과 비교하며 갱신하면 됩니다.

	 while (!pq.empty()) {
		 int left = pq.top();
		 if (y - left <= d) {
			 break;
		 } else {
			 pq.pop();
		 }
	 }
	 ans = std::max(ans, (int)pq.size());
}

백준 1945번: 직사각형

원점에서 각 사각형의 왼쪽 상단 모서리와 오른쪽 하단 모서리까지를 연결한 선의 기울기 각도를 통해 스위핑을 진행합니다.

기울기의 각도는 atan2를 통해 알 수 있습니다.

왼쪽 상단 모서리는 1, 오른쪽 하단 모서리는 -1로 설정하여 구분할 수 있도록 하였습니다.

for (int i = 0; i < n; ++i)
	double left_top = atan2(ytr, xbl);
	double right_bottom = atan2(ybl, xtr);
	v.push_back({right_bottom, -1});        
	v.push_back({left_top, 1});
}

제일 기울기가 큰 모서리부터 살펴보도록 정렬을 하고

count 변수에 왼쪽 상단 모서리를 지나가면 1을 더해주고 오른쪽 하단 모서리를 지나가면 -1을 빼줍니다.

이후 count변수의 최댓값을 찾으면 됩니다.

std::sort(v.begin(),v.end(), std::greater<std::pair<double, int>>());

int ans = 0;
int count = 0;
for (int i = 0; i < 2 * n; ++i) {
	auto [p, w] = v[i];
	count += w;
	ans = std::max(ans, count);
}

std::cout << ans;