[백준] 10165 - 버스 노선

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

💎 문제 조건과 설명

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

🚀 생각한 아이디어

만약 노선들이 [1,4], [1,3], [2,5], [3, 6] 등 중간에 0을 거치는 노선이 없는 경우 (즉, a > b 인 노선이 없는 경우)에는 일반적인 라인스위핑 문제처럼 버스 정류소의 갯수만큼만 탐색을 진행하면 됩니다.

그러나 이 문제는 a > b인 노선, 즉, 중간에 0을 거치는 노선이 포함될 수 있으므로 그 부분만 유의해서 생각하면 됩니다.

예시로 [0, 4], [2, 3], [2, 6], [5, 0], [8, 4], [9, 1] 의 6가지 노선이 있다고 가정한 후 그림과 같이 풀어보도록 하겠습니다.

먼저, 라인 스위핑을 위해 각 노선들을 시작점을 기준으로 오름차순 정렬해 놓습니다. 시작점이 동일하면, 끝점을 기준으로 내림차순 정렬해 놓습니다.

포함 관계는 크게 세 가지로 볼 수 있습니다.

case 1 : a < b 인 노선들 간의 포함 여부 파악

a < b인 노선에는 [0, 4], [2, 3], [2, 6] 이 있습니다.

a < b인 노선들은 각 노선들이 일렬로 있다고 가정하고 라인 스위핑으로 풀면 됩니다. 각 노선들을 정렬한 결과, 아래와 같습니다.

이제 정렬된 노선들을 가지고, 도착점을 기준으로 라인 스위핑 하면서 포함 관계를 파악합니다. 초기 right 값은 0 입니다.

지금 보고 있는 노선의 끝점이 6이므로 이전 노선에서 갱신된 도착점 right보다 큽니다. 따라서 이전 노선에 포함 관계는 없으며 right 값을 갱신합니다.

지금 보고 있는 노선의 끝점이 3이므로, 이전 노선에서 갱신된 도착점 right보다 작습니다. 따라서 포함 관계가 성립하며, right 값은 갱신하지 않습니다. 이 때 포함된 노선에는 별도 배열에 false 등을 기록하여 운행 취소 여부를 저장해 둡니다.

case 2 : a > b(0을 거치는) 노선 안에, a < b인 노선이 포함되는지 파악

[5, 0], [8, 4], [9, 1] 노선 안에, a < b인 [0, 4], [2, 3], [2, 6] 들이 포함되는지 파악해야 합니다.

a < b인 노선을 일반적인 노선이라고 부르겠습니다.

0을 거치는 노선들은 아래와 같이 나타낼 수 있습니다.

위에서 0을 거치는 노선들의 시작점 중에서 가장 작은 시작점은 5 입니다. 0을 거치는 노선들의 도착점 중에서 가장 큰 도착점은 4 입니다. 이들을 각각 minA와 maxB 로 칭하겠습니다. 여기서 두 가지 특성을 발견할 수 있습니다.

첫 번째 경우 : 일반적인 노선의 시작점 a가, minA 보다 크거나 같다면, 반드시 0을 거치는 노선 안에 포함됩니다.
두 번째 경우 : 일반적인 노선의 도착점 b가, maxB 보다 작거나 같다면, 반드시 0을 거치는 노선 안에 포함됩니다.

첫 번째 경우 : a < b인 노선 중 [0, 4], [2, 3] 노선들이 [8, 4] 안에 포함됩니다.

두 번째 경우 : 예시에는 없지만 만약에 [7, 9] 라는 노선이 있었다면, [5, 0] 안에 포함될 것입니다.

즉, 예를 들어 [5, 6], … [5,9], …, [8, 9] 등이 0을 거치는 노선 안에 포함될 수 있습니다. 모두 minA = 5보다 시작점이 크거나 같은 것을 볼 수 있습니다.

그리고 [0, 1],…,[0, 4], [1, 2], …[1, 4],[2, 3],[2, 4],[3, 4] 등이 0을 거치는 노선 안에 포함될 수 있습니다. 모두 maxB = 4 보다 도착점이 작거나 같은 것을 볼 수 있습니다.

case 3 : a > b(0을 거치는) 노선들 간의 포함 여부 파악

0을 거치는 노선 안에, 또다른 0을 거치는 노선이 포함되는지를 파악해야 합니다.

이것은 case 1과 유사하게 라인 스위핑으로 구할 수 있습니다.

하나만 변화시키면 되는데, 예를 들어, [9, 1] 이 [8, 4] 에 포함되는지 알고 싶으면 각각 [9, 11] 과 [8, 14] 로 변경시킨 다음, case 1 방식 그대로 라인 스위핑을 해 보면 됩니다.

즉, 도착점에 +N 을 해놓고 case 1 방식을 그대로 사용하면 됩니다.

[참고] 일반적인 노선 안에 0을 거치는 노선이 포함되는 경우는 없습니다.

📜 소스코드(C++)

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>

#define ll long long
#define pii pair<int,int>

using namespace std;

ll N, M;
typedef struct bus {
	int num, a, b;
}Bus;

vector<Bus> route1, route2;
bool compare(const Bus& f, const Bus& s) {
	if (f.a != s.a) return f.a < s.a;
	else return f.b > s.b;
}

bool able[500001];
int main() {

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

	cin >> N;
	cin >> M;

	ll minA = 1e12, maxB = -1;

	for (int i = 1; i <= M; i++) {
		ll a, b; cin >> a >> b;
		Bus bus;
		bus.num = i; bus.a = a; bus.b = b;
        
		/* a < b인 경우(0을 거치지 않음)*/
		if (a - b <= 0) {
			route1.push_back(bus);
		}
        /* a > b인 경우(0을 거침) */
		else {
			minA = min(minA, a);
			maxB = max(maxB, b);
			bus.b = b + N;
            
			route2.push_back(bus);
		}
		able[i] = true;
	}

	sort(route1.begin(), route1.end(), compare);
	sort(route2.begin(), route2.end(), compare);

	int right = 0;
    
    /* 0을 거치지 않는 일반적인 노선 처리 */
	for (int i = 0; i < route1.size(); i++) {
		// 0을 거치지 않는 일반적인 노선의 시작점이
		// 0을 거치는 노선의 시작점보다 뒤에 있으면,
		// 반드시 0을 거치는 노선 안에 포함된다.

		// 혹은, 0을 거치지 않는 일반적인 노선의 도착점이
		// 0을 거치는 노선의 도착점보다 앞에 있으면,
		// 반드시 0을 거치는 노선 안에 포함된다.
		if (minA <= route1[i].a) able[route1[i].num] = false;
		if (maxB >= route1[i].b) able[route1[i].num] = false;

		// 일반적인 경우
		if (route1[i].b <= right) {
			able[route1[i].num] = false; // 포함되었으니 삭제
		}
		else {
			right = route1[i].b;
		}
	}

	/* 0을 거치는(즉, a > b인 노선) 노선 처리 */
	right = 0;
	for (int i = 0; i < route2.size(); i++) {
		// 일반적인 경우로 취급
		if (route2[i].b <= right) {
			able[route2[i].num] = false; // 포함되었으니 삭제
		}
		else {
			right = route2[i].b;
		}
	}

	for (int i = 1; i <= M; i++) {
		if (able[i] == true) {
			cout << i << ' ';
		}
	}

	return 0;
}

[백준] 10165 - 버스 노선