[BOJ 10165] 버스 노선

BOJ 10165 버스 노선

유형

• 그리디

풀이

정렬이 중요한 문제라고 생각되었다.
시작 시점을 기준으로 오름차순정렬하고 시작 지점이 같으면 끝 지점이 더 멀리 있는 것이 앞으로 정렬되게 하였다.

정렬된 각 노선들을 순회하면서 다음 노선의 끝 지점이 현재 노선의 끝 지점보다 크면 현재 노선에 포함되지 않으므로 카운트를 하나씨 늘려주는 방식으로 처리하였다.

여기까지는 구현가능 하였지만 마지막 노선의 끝 지점이 정류소 0번을 넘어서 앞 노선들을 포함하는 경우를 처리하는데 어려움을 겪었다다.

예를들어 N = 10일때 마지막 노선과 처음 노선이 (6,9) (0,5) 이렇게 주어질 때에는 마지막 노선이 처음 노선을 포함하지 않지만 (6,4) (0,3) 이런식으로 주어지게 되면 마지막 노선이 처음 노선을 포함하기 때문에 처음 노선을 제외를 시켜주어야 한다.

이것을 처리하기 위해서 처음 입력을 받을 때 노선의 시작지점이 끝 지점보다 클 경우(정류소 0번을 포함하면서 넘어올경우) 끝 지점의 최대값을 저장해두었다.

그리고 선별된 노선들의 처음부터 순회하며 끝 지점이 위에 저장된 끝지점의 최대값보다 작을 경우 포함된다고 판단하여 해당 노선을 제외하는 방식으로 구현하였다.

앞과 뒤에서 삽입, 삭제가 필요했어서 deque 자료구조를 사용하였다. 그리고 계산의 편의를 위해서 입력을 받을 때 시작지점이 끝 지점보다 크면 끝 지점에 + N을 해주는 전처리 과정이 필요했다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <deque>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n, m, back = 0;
struct info { int s, e, i; } v[500001];
set<int> ans;
deque<info> dq;

bool cmp(info a, info b) { return a.s == b.s ? (a.e > b.e) : (a.s < b.s); }

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);

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

	sort(v, v + m, cmp);

	for (int i = 0; i < m; i++) {
		if (dq.empty() || dq.back().e < v[i].e) dq.push_back(v[i]);
	}
	while (!dq.empty() && dq.front().e <= back) dq.pop_front();

	for (int i = 0; i < dq.size(); i++) ans.insert(dq[i].i);
	for (int x : ans) cout << x << ' ';
	return 0;
}