백준10165 버스 노선

작성일 | In

문제 링크

  • http://icpc.me/10165

문제 출처

  • 2014 전국 본선 초등부4, 중등부3, 고등부2

사용 알고리즘

  • 스위핑

시간복잡도

  • O(MlgM)

풀이

모든 노선은 N-1번과 0번 사이에 있는 도로를 지나는 정점과 안 지나는 정점, 두 가지로 분류할 수 있습니다.
안 지나는 노선을 A그룹, 지나는 노선을 B그룹이라고 하겠습니다.

A그룹에 있는 두 노선 a, b는 아래 조건을 만족하면 a가 없어져도 됩니다. b.start <= a.start < a.end <= b.end
A그룹의 원소들을 먼저 시작하는 노선이 앞쪽에, 시작하는 지점이 같다면 늦게 끝나는 노선이 앞쪽에 오도록 정렬을 합시다. 그러면 뒤에 있는 노선이 앞에 있는 노선을 포함하는 경우가 없습니다.

B그룹을 처리하는 방법을 알아봅시다.
A그룹에 있는 노선이 B그룹에 있는 노선을 포함하는 경우는 없습니다. 그러므로 B그룹의 노선이 A그룹의 노선을 포함하는 경우와, B그룹의 노선이 또 다른 B그룹의 노선을 포함하는 경우만 보면 됩니다.
B그룹의 노선이 또 다른 B그룹의 노선을 포함하는 경우는 노선의 종료 지점에 N을 더한 뒤, A그룹과 같이 처리를 해주면 됩니다.

마지막으로, B그룹의 노선이 A그룹의 노선을 포함하는 경우입니다.

빨간색을 A그룹의 노선, 초록색을 B그룹의 노선이라고 하면, A그룹 노선의 종료지점보다 B그룹 노선의 종료지점이 더 뒤에 있으면 A가 B에 포함이 됩니다.
그러므로 B그룹의 노선들의 종료지점의 최댓값을 구한 뒤, A그룹의 노선들과 비교해주면 됩니다.

구현 방법은 코드를 참고하시면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

struct asdf{
	int s, e, x;
	bool operator < (asdf &x){
		if(s == x.s) return e > x.e;
		return s < x.s;
	}
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	vector<asdf> v(m);

	int back = 0; //0을 지나는 노선의 종점의 최댓값

	for(int i=0; i<m; i++){
		cin >> v[i].s >> v[i].e;
		v[i].x = i+1;
		if(v[i].s > v[i].e){
			back = max(back, v[i].e);
			v[i].e += n;
		}
	}
	sort(v.begin(), v.end());

	deque<asdf> dq;
	for(auto i : v){
		if(dq.empty() || dq.back().e < i.e) dq.push_back(i);
	}
	while(!dq.empty() && dq.front().e <= back) dq.pop_front();
	sort(dq.begin(), dq.end(), [&](asdf &a, asdf &b){
		return a.x < b.x;
	});
	for(auto i : dq) cout << i.x << " ";
}