[백준] 13334번 - 철로

[링크] https://www.acmicpc.net/problem/13334

💎 문제 조건과 설명

문제 조건과 설명은 위의 링크를 참조 부탁드립니다.

🚀 생각한 아이디어

라인 스위핑 문제를 많이 접하지 않아서 그런지 풀이 시간이 좀 오래 걸렸습니다..
라인 스위핑 문제는 정렬된 어떤 자료에서 시간 복잡도를 줄일 수 있도록 선을 한 번만 훑으면서 최종 결과를 찾는 방식으로 되어 있습니다. 이 때 우선순위 큐가 자주 사용된다고 합니다.
길이가 d인 선분 L 안에 포함되는 사람들을 탐색하는 과정 자체는 아래와 같이 떠올릴 수 있습니다.

먼저 정수쌍을 도착 지점 오름차순으로 정렬합니다. 도착 지점이 같을 경우, 출발 지점의 오름차순으로 정렬합니다. 그리고 아래와 같은 과정으로 찾아나갑니다.

검은색 선분은 정렬된 사람들, 빨간색 선분은 길이가 d인 철로 선분 L이고, 파란색 선분은 직선 L에 포함될 수 있는 사람들을 의미합니다.

(1) 사람들을 정렬한 상태입니다. 그리고 오른쪽 끝값이 제일 작은 사람부터 차례대로 선분 L에 들어올 수 있는지 살펴 봅니다.

(2) 길이가 d인 선분 L 안에 (10, 20) 인 사람은 포함될 수 있습니다. - 현재 최댓값 : 1

(3) 선분 L을 다음으로 옮긴 뒤 (10, 25) 인 사람은 포함될 수 있습니다. - 현재 최댓값 : 2

(4) 선분 L을 옮긴 뒤 (25, 30) 사람은 포함될 수 있습니다. - 현재 최댓값 : 3

(5) 선분 L을 옮긴 뒤 (25, 35) 인 사람은 포함될 수 있습니다. - 현재 최댓값 : 4

(6) 선분 L을 옮긴 뒤, 다음 사람은 (5, 40) 이지만 길이가 35이므로, 선분 L보다 길기 때문에 고려하지 않고 바로 다음 사람인 (30, 50)으로 선분 L을 옮겼습니다.
선분 L 안에 (30, 50)인 사람은 포함될 수 있습니다. 이 때 기존에 포함되어 있던 (10, 20) 과 (10, 25) 두 사람은 가능한 선분에서 제외되었습니다. 선분 L에 포함된 사람의 숫자는 3명이고 지금까지 최댓값은 4입니다.

(7) 선분 L을 옮긴 뒤 (50, 60) 인 사람은 포함될 수 있습니다. 기존에 포함되어 있던 (25, 30) 과 (25, 35) 두 사람은 가능한 선분에서 제외되었습니다. - 현재 최댓값 : 4

(8) 선분 L을 옮긴 뒤 (80, 100) 인 사람은 포함될 수 있습니다. - 현재 최댓값 : 4

이러한 과정을 거쳐서 최댓값 4 라는 최종 결과를 얻을 수 있습니다.

이 문제를 구현할 때 중요한 것은

사람들을 끝점을 기준으로 오름차순 정렬 하는 것과
위 그림에서 매 상황마다 가능한 사람들의 왼쪽 시작점을 담아 두는 우선순위 큐 (가능한 사람들이란 그림에서 파란색 선분을 말합니다)

가 있어야 한다는 점입니다. 해당 우선순위 큐는 최소 힙으로 작동해야 합니다.

즉, 매번 돌 때마다 그림에서의 파란색 선분 갯수는 우선순위 큐의 크기와 동일합니다. 따라서 최댓값을 갱신할 때는 우선순위 큐의 크기를 가지고 하면 됩니다.

그렇다면 왜 최소 힙으로 동작하는 우선순위 큐를 사용해야 할까요?

그림 (1) ~ (5)의 과정까지는 문제 없이 현재 선분 L에 포함되는 사람들만 만났고, 그 다음 그림 (6) 과정을 살펴 보겠습니다.

그림 (6)에서 처음 만난 (30, 50) 인 사람은 선분 L에 들어올 수 있으므로 우선순위 큐에 왼쪽 시작점 30을 넣습니다.
이후 기존에 우선순위 큐에 들어 있던 사람들이 계속 선분 L에 포함될 수 있는지 확인해야 합니다. 이 때, 우선순위 큐가 최소 힙으로 동작하면 가장 작은 시작점을 갖는 사람부터 확인할 수 있습니다. 이 때는 (10, 20)인 사람의 시작점 10부터 확인하게 됩니다.
(10, 20) 인 사람의 시작점인 10과, 새로 만난 (30, 50) 인 사람의 끝점 50 사이의 거리는 40인데, 선분 L의 거리인 30보다 깁니다. 따라서 그림 (6)에서 선분 L이 (30, 50)과 (10, 20)을 모두 포함할 수 없으므로 (10, 20)의 시작점인 10을 우선순위 큐에서 pop해서 없앱니다.
마찬가지로 (10, 25) 인 사람에 대해서도 똑같이 진행하면 (10, 25)의 시작점 10도 우선순위 큐에서 pop해서 없어집니다.
그 다음 사람인 (25 ,30)을 보겠습니다. (25, 30)의 시작점 25와 현재 처음 만난 (30, 50)의 끝점 50 사이의 거리는 20 이므로 현재 선분 L은 (25, 30)과 (30, 50) 모두 포함할 수 있습니다. 따라서 우선순위 큐 확인은 그만하고 다음으로 가능한 사람을 찾으러 갑니다.(그림 (7)로 감)

그림에서 보면 선분 L을 다음 사람의 끝점으로 옮긴 다음에 사람들이 포함될 수 있는지 비교하고 있습니다.
이 과정은 위에서 살펴본 새로 만난 선분의 끝점과 기존에 포함되었던 선분의 시작점을 비교하는 것과 같은 상황으로 보면 됩니다.

📜 소스코드(C++)

주석으로 최대한 자세히 써 놓았으니 참고해 주세요!

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

#define pii pair<int, int>

int n, d;
vector<pair<int, int>> input;
vector<pii> inputQ;
priority_queue<int, vector<int>, greater<int>> pq;

bool compare(const pair<int, int>& a, const pair<int, int>& b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else if (a.second == b.second) {
		return a.first < b.first;
	}
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int h, o;
		cin >> h >> o;
		if (h > o)inputQ.push_back({ o,h });
		else inputQ.push_back({ h,o });
	}
	cin >> d;

	// 끝 점 o를 기준으로 (h, o) pair를 오름차순 정렬
	sort(inputQ.begin(), inputQ.end(), compare);

	int maxSize = 0;

	// 정렬된 모든 쌍을 차례대로 살펴본다.
	for(int i = 0; i<inputQ.size(); i++){
		int iR = inputQ[i].second;
		int iL = inputQ[i].first;

		// iR-iL 사이즈, 즉 사람의 길이가 d보다 작으면
        // 일단 선분 L 안에 들어올 수 있는 후보니까 그 시작점을 우선순위 큐에 넣는다.
		if (iR - iL <= d) {
			pq.push(iL);
		}
		else continue;

		while (!pq.empty()) {
			// 가능한 왼쪽 시작점 후보들이 있는 pq 에서 하나를 뽑아서
			// 현재 살펴보고 있는 i번째 사람의 오른쪽 끝값과의 거리를 계산하고
			// 그 거리가 d 이하이면 나가서 다른 인풋을 계속 보며,
			// d 보다 큰 거리이면 후보에서 빼버린다. (pop)
			int tmp = pq.top();
			if (iR - tmp <= d) break;
			else 
				pq.pop();		
		}
		maxSize = max(maxSize, (int)pq.size());
	}

	cout << maxSize;
	return 0;
}

[백준] 13334번 - 철로