BOJ 10165 : 버스 노선

• 문제 링크 : boj.kr/10165
• 난이도 : P5
• 태그 : 정렬, 스위핑

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

struct route {
    ll s;
    ll e;
    int idx;
    route(ll _s, ll _e, int _idx) : s(_s), e(_e), idx(_idx) {}
};

bool comp(route &a, route &b) {
    if(a.s == b.s) return a.e > b.e;
    return a.s < b.s;
}

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

    int n, m;
    cin >> n >> m;
    vector<bool> check(m+1, true);
    vector<route> routes;
    for(int i = 1; i <= m; i++) {
        ll a, b;
        cin >> a >> b;
        if(b < a) b += n;
        routes.emplace_back(a, b, i);
        routes.emplace_back(a+n, b+n, i);
    }
    sort(all(routes), comp);
    ll M = 0;
    for(int i = 0; i < routes.size(); i++) {
        if(routes[i].e <= M) {
            check[routes[i].idx] = false;
        }
        M = max(M, routes[i].e);
    }

    for(int i = 1; i <= m; i++) {
        if(check[i]) cout << i << " ";
    }

    return 0;
}

---

풀이

원으로 주어진 입력을 직선으로 만들어준다.

원으로 된 입력은 두 바퀴를 돌리면 직선처럼 생각할 수 있다.

이후에 출발점을 기준으로 오름차순, 출발점이 같다면 도착점을 기준으로 내림차순으로 정렬한다.

정렬했을 때 어떤 노선 i가 이전의 이전 노선들 도착점의 최댓값보다 작다면 포함되는 노선이므로 제거하면 된다.